P9193 [USACO23OPEN] Good Bitstrings P

题目描述

对于任意两个正整数 $a$ 和 $b$，定义函数 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+b$ 的比特串，其中恰好包含 $a$ 个零和 $b$ 个一。例如，gen_string(4,10)=01110110111011。

称一个 $0/1$ 串 $s$ 是好的，如果存在正整数 $x$ 和 $y$，使得 $s = \text{gen\_string}(x,y)$。给定两个正整数 $A$ 和 $B$ $(1 \le A, B \le 10^{18})$，你的任务是计算 gen_string(A,B) 的所有好前缀的数量。例如，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

输入格式

第一行包含 $T$ $(1 \le T \le 10)$，表示独立测试用例的数量。

接下来的 $T$ 行，每行包含两个整数 $A$ 和 $B$。

输出格式

每个测试用例的答案单独占一行。

输入输出样例 1

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

1
5
7
10
6
13

说明/提示

输入 $2$：$A, B \le 100$；
输入 $3$：$A, B \le 1000$；
输入 $4-7$：$A, B \le 10^6$；
输入 $8-13$：所有答案不超过 $10^5$；
输入 $14-21$：没有额外限制。