A6156. 「USACO 2023 US Open Platinum」Good Bitstrings
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 US Open Contest, Platinum](http://usaco.org/index.php?page=open23results) Problem 2. [Good Bitstrings](http://usaco.org/index.php?page=viewproblem2&cpid=1333)**
对于任意正整数 $a$ 和 $b$，定义函数 $\texttt{gen_string}(a,b)$ 如以下 Python 代码所示：
```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++ 代码如下：
```cpp
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$ 个 $0$ 和 $b$ 个 $1$。例如，$\texttt{gen_string}(4, 10)=01110110111011$。
如果存在正整数 $x$ 和 $y$ 使得二进制串 $s=\texttt{gen_string}(x,y)$，则称这个二进制串 $s$ 是好的。给定两个正整数 $A$ 和 $B\ (1\le A,B\le 10^{18})$，你的任务是计算 $\texttt{gen_string}(A,B)$ 的好前缀的数量。例如，$\texttt{gen_string}(4,10)$ 有 $6$ 个好前缀，如下所示：
| $x$ | $y$ | $\texttt{gen_string}(x,y)$ |
| :--: | :--: | :-------------------------: |
| $1$ | $1$<!-- 0 --> | $01$ |
| $1$<!-- 0 --> | $2$ | $011$ |
| $1$ | $3$ | $0111$ |
| $2$ | $5$ | $0111011$ |
| $3$ | $7$ | $0111011011$ |
| $4$ | $10$ | $01110110111011$ |
对于任意正整数 $a$ 和 $b$，定义函数 $\texttt{gen_string}(a,b)$ 如以下 Python 代码所示：
```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++ 代码如下：
```cpp
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$ 个 $0$ 和 $b$ 个 $1$。例如，$\texttt{gen_string}(4, 10)=01110110111011$。
如果存在正整数 $x$ 和 $y$ 使得二进制串 $s=\texttt{gen_string}(x,y)$，则称这个二进制串 $s$ 是好的。给定两个正整数 $A$ 和 $B\ (1\le A,B\le 10^{18})$，你的任务是计算 $\texttt{gen_string}(A,B)$ 的好前缀的数量。例如，$\texttt{gen_string}(4,10)$ 有 $6$ 个好前缀，如下所示：
| $x$ | $y$ | $\texttt{gen_string}(x,y)$ |
| :--: | :--: | :-------------------------: |
| $1$ | $1$<!-- 0 --> | $01$ |
| $1$<!-- 0 --> | $2$ | $011$ |
| $1$ | $3$ | $0111$ |
| $2$ | $5$ | $0111011$ |
| $3$ | $7$ | $0111011011$ |
| $4$ | $10$ | $01110110111011$ |
输入格式
第一行一个整数 $T\ (1\le T\le 10)$，表示互相独立的测试点个数。
接下来 $T$ 行，每行两个整数 $A$ 和 $B$。
接下来 $T$ 行，每行两个整数 $A$ 和 $B$。
输出格式
对于每个测试点，输出一行表示答案。
输入输出样例
输入 #1
6 1 1 3 5 4 7 8 20 4 10 27 21
输出 #1
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 组数据：无附加限制
- 第 3 组数据：$A,B\le 1000$
- 4-7 组数据：$A,B\le 10^6$
- 8-13 组数据：所有答案最多为 $10^5$
- 14-21 组数据：无附加限制