#P9193. [USACO23OPEN] Good Bitstrings P
[USACO23OPEN] Good Bitstrings P
题目描述
For any two positive integers and , define the function gen_string(a,b)
by the following Python code:
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
Equivalent C++ code:
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;
}
will equal and will equal when the loop terminates, so this function returns a bitstring of length with exactly zeroes and ones. For example, gen_string(4,10)=01110110111011
.
Call bitstring good if there exist positive integers and such that s=gen_string(x,y)
. Given two positive integers and , your job is to compute the number of good prefixes of gen_string(A,B)
. For example, there are good prefixes of gen_string(4,10)
:
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
输入格式
The first line contains , the number of independent test cases.
Each of the next lines contains two integers and .
输出格式
The answer for each test case on a new line.
题目大意
题目描述
对于任意两个正整数 和 ,定义函数 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;
}
当循环结束时, 将等于 , 将等于 ,因此该函数返回一个长度为 的比特串,其中恰好包含 个零和 个一。例如,gen_string(4,10)=01110110111011
。
称一个 串 是好的,如果存在正整数 和 ,使得 。给定两个正整数 和 ,你的任务是计算 gen_string(A,B)
的所有好前缀的数量。例如,gen_string(4,10)
有 个好前缀:
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
输入格式
第一行包含 ,表示独立测试用例的数量。
接下来的 行,每行包含两个整数 和 。
输出格式
每个测试用例的答案单独占一行。
提示
输入 :;
输入 :;
输入 :;
输入 :所有答案不超过 ;
输入 :没有额外限制。
6
1 1
3 5
4 7
8 20
4 10
27 21
1
5
7
10
6
13
提示
Input : ;
Input : ;
Inputs : ;
Inputs : All answers are at most .
Inputs : No additional constraints.