Задача . Good Bitstrings

Для любых двух положительных целых чисел \(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(int64t a, int64t 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+b\), содержащую ровно \(a\) нулей и \(b\) единиц. Например, \(\texttt{gen_string}(4,10)=01110110111011\).

Назовём строку битов \(s\) \(\textbf{хорошей}\), если существуют положительные целые числа \(x\) и \(y\) такие, что \(s=\texttt{gen_string}(x,y)\). Даны два натуральных числа \(A\) и \(B\) (\(1\le A,B\le 10^{18}\)), ваша задача состоит в том, чтобы вычислить количество хороших префиксов \(\texttt{gen_string}(A,B)\). Например, есть \(6\) хороших префиксов \(\texttt{gen_string}(4,10)\):

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

ОБРАЗЕЦ ВВОДА:

6
1 1
3 5
4 7
8 20
4 10
27 21

ОБРАЗЕЦ ВЫВОДА:

1
5
7
10
6
13

Автор: Benjamin Qi

1
5
7
10
6
13