#P9193. [USACO23OPEN] Good Bitstrings P

[USACO23OPEN] Good Bitstrings P

题目描述

For any two positive integers aa and bb, 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;
}

iaia will equal aa and ibib will equal bb when the loop terminates, so this function returns a bitstring of length a+ba+b with exactly aa zeroes and bb ones. For example, gen_string(4,10)=01110110111011.

Call aa bitstring ss good if there exist positive integers xx and yy such that s=gen_string(x,y). Given two positive integers AA and BB (1A,B1018)(1\le A,B\le10^{18}), your job is to compute the number of good prefixes of gen_string(A,B). For example, there are 66 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 TT (1T10)(1\le T\le10), the number of independent test cases.

Each of the next TT lines contains two integers AA and BB.

输出格式

The answer for each test case on a new line.

题目大意

题目描述

对于任意两个正整数 aabb,定义函数 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;
}

当循环结束时,iaia 将等于 aaibib 将等于 bb,因此该函数返回一个长度为 a+ba+b 的比特串,其中恰好包含 aa 个零和 bb 个一。例如,gen_string(4,10)=01110110111011

称一个 0/10/1ss好的,如果存在正整数 xxyy,使得 s=gen_string(x,y)s = \text{gen\_string}(x,y)。给定两个正整数 AABB (1A,B1018)(1 \le A, B \le 10^{18}),你的任务是计算 gen_string(A,B) 的所有好前缀的数量。例如,gen_string(4,10)66 个好前缀:

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

输入格式

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

接下来的 TT 行,每行包含两个整数 AABB

输出格式

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

提示

输入 22A,B100A, B \le 100
输入 33A,B1000A, B \le 1000
输入 474-7A,B106A, B \le 10^6
输入 8138-13:所有答案不超过 10510^5
输入 142114-21:没有额外限制。

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

1
5
7
10
6
13

提示

Input 22: A,B100A,B\le100;
Input 33: A,B1000A,B\le1000;
Inputs 474-7: A,B106A,B\le10^6;
Inputs 8138-13: All answers are at most 10510^5.
Inputs 142114-21: No additional constraints.