Good Bitstrings

题目描述

对于任意两个正整数 $a$ 和 $b$，按如下 Python 代码定义函数 \texttt{gen_string}(a,b)： def gen_string(a: int, b: int): \tres = "" \tia, ib = 0, 0 \twhile ia + ib < a + b: \t\tif ia * b <= ib * a: \t\t\tres += '0' \t\t\tia += 1 \t\telse: \t\t\tres += '1' \t\t\tib += 1 \treturn res 等价的 C++ 代码： string gen_string(int64_t a, int64_t b) { \tstring res; \tint ia = 0, ib = 0; \twhile (ia + ib < a + b) { \t\tif ((__int128)ia * b <= (__int128)ib * a) { \t\t\tres += '0'; \t\t\tia++; \t\t} else { \t\t\tres += '1'; \t\t\tib++; \t\t} \t} \treturn res; } 循环结束时，$ia$ 将等于 $a$ 且 $ib$ 将等于 $b$，因此该函数会返回一个长度为 $a+b$ 的二进制字符串，其中恰好包含 $a$ 个 0 和 $b$ 个 1。例如，\texttt{gen_string}(4,10)=01110110111011。

若一个二进制字符串 $s$ 满足存在正整数 $x$ 和 $y$ 使得 s=\texttt{gen_string}(x,y)，则称 $s$ 为\textbf{好（good）}的。给定两个正整数 $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

输入格式

第一行包含 $T$（$1\le T\le 10$），表示相互独立的测试用例数量。 接下来 $T$ 行每行包含两个整数 $A$ 和 $B$。

输出格式

对每个测试用例输出一行答案。

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

1
5
7
10
6
13

提示

SCORING: Input 2: $A,B\le 100$ Input 3: $A,B\le 1000$ Inputs 4-7: $A,B\le 10^6$ Inputs 8-13: 所有答案均不超过 $10^5$。 Inputs 14-21: 无额外限制。 题目贡献者：Benjamin Qi

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum