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

문제 설명

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

Input
첫번째 줄에는 테스트 케이스의 수 $t (1 \le t \le 10^4)$이 주어진다.

각 테스트 케이스는 두 정수 $l, r(1 \le l \le r \le 10^9)$ 가 주어진다.

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 \le [\frac{n - 1}{2}]$ 그리고 이 최대값을 만족하는 $b$값은 $b = [\frac{n}{2}] + 1$ 이다.

따라서 $l$이 $b$보다 작거나 같으면 $b$를 $[\frac{n}{2}] + 1$로 선택할 수 있기 때문에 최대값은 $[\frac{n - 1}{2}]$이다.

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

정답 코드

#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;
}