알고리즘/codeforces

Codeforces Round #741 (Div. 2)-A. The Miracle and the Sleeper

falconlee236 2021. 12. 19. 15:29
반응형

문제 설명

두 정수 l, r이 주어진다.(lr) rabl 을 만족하는 (a,b)쌍 중에서 amodb의 값이 최대가 되는 쌍을 찾아라.

Input
첫번째 줄에는 테스트 케이스의 수 t(1t104)이 주어진다.

각 테스트 케이스는 두 정수 l,r(1lr109) 가 주어진다.

Output
각 테스트케이스마다 문제에 맞는 답을 출력한다.

Example
input
4
1 1
999999999 1000000000
8 26
1 999999999

output
0
1
12
499999999

문제 접근

사용한 알고리즘: 구현, 수학, 정수론
걸린 시간 : 00:04
A번 답게 조금만 생각하면 풀 수 있는 문제지만 이 문제에 놀라운 정수론이 숨어 있었고, 그 사실을 editorial을 보면서 알게됐다. 이게 업솔빙의 중요성이라는 사실을 다시금 깨닫게 한다.

a;mod;b는 이 식을 반드시 만족한다. a;mod;b[n12] 그리고 이 최대값을 만족하는 b값은 b=[n2]+1 이다.

따라서 lb보다 작거나 같으면 b[n2]+1로 선택할 수 있기 때문에 최대값은 [n12]이다.

만약 lb보다 크다면 최대값을 만족하는 b값을 선택할 수 없다. 그러면 a;mod;bab를 항상 만족한다.

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);
    int t; cin >> t;
    while(t--){
        int l, r; cin >> l >> r;
        cout << (r / 2 + 1 < l ? r - l : (r - 1) / 2) << "\n";
    } 
    return 0;
}
반응형