좋은 비트 문자열

임의의 두 양의 정수 \(a\)와 \(b\)에 대해, 함수 \(\texttt{gen_string}(a,b)\)를 다음 Python 코드로 정의한다:

def gen_string(a: int, b: int):
    res = ""
    ia, ib = 0, 0
    while ia + ib < a + b:
        if ia * b <= ib * a:
            res += '0'
            ia += 1
        else:
            res += '1'
            ib += 1
    return res

동등한 C++ 코드:

string gen_string(int64_t a, int64_t b) {
    string res;
    int ia = 0, ib = 0;
    while (ia + ib < a + b) {
        if ((__int128)ia * b <= (__int128)ib * a) {
            res += '0';
            ia++;
        } else {
            res += '1';
            ib++;
        }
    }
    return res;
}

루프가 종료될 때 \(ia\)는 \(a\)와 같고 \(ib\)는 \(b\)와 같으므로, 이 함수는 정확히 \(a\)개의 0과 \(b\)개의 1을 가진 길이 \(a+b\)의 비트 문자열을 반환한다. 예를 들어 \(\texttt{gen_string}(4,10)=01110110111011\)이다.

비트 문자열 \(s\)에 대해 \(s=\texttt{gen_string}(x,y)\)를 만족하는 양의 정수 \(x\)와 \(y\)가 존재하면 \(s\)를 \(\textbf{좋은}\) 문자열이라 부른다. 두 양의 정수 \(A\)와 \(B\) (\(1\le A,B\le 10^{18}\))가 주어질 때, \(\texttt{gen_string}(A,B)\)의 좋은 접두사의 개수를 계산하는 것이 당신의 임무이다. 예를 들어 \(\texttt{gen_string}(4,10)\)의 좋은 접두사는 \(6\)개이다:

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

출제자: Benjamin Qi

배점

• 입력 2: \(A,B\le 100\)
• 입력 3: \(A,B\le 1000\)
• 입력 4-7: \(A,B\le 10^6\)
• 입력 8-13: 모든 답이 \(10^5\) 이하이다.
• 입력 14-21: 추가 제약 조건이 없다.

출제자: Benjamin Qi

첫째 줄에 독립적인 테스트 케이스의 개수 \(T\) (\(1\le T\le 10\))가 주어진다.

다음 \(T\)개의 줄에는 각각 두 정수 \(A\)와 \(B\)가 주어진다.

각 테스트 케이스의 답을 새 줄에 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > US Open > Platinum