分数: 400 点
问题陈述
对于正整数 x 和 y,定义 f(x,y) 如下:
- 让 z 为解释得到的字符串 x,y 以十进制表示为字符串,并按此顺序连接它们。让 f(x,y) 是当 z 被解释为十进制整数。
例如, f(3,14)=314,\ f(100,3)=1003.
给你正整数 C 和 D。求整数的个数 x 满足以下条件:
- 1 \leq x \leq D
- f(C, C+x) 是一个完美的正方形。
你被给予 T 测试用例,找到每个用例的答案。
约束
- 1 \leq T \leq 3 \times 10^5
- 1 \leq C \leq 2 \times 10^8
- 1 \leq D \leq 5 \times 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i 代表 i- 第一个测试用例。每个测试用例均按以下格式给出:
C D
输出
输出 T 行。的 i- 第行 (1 \leq i \leq T)应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 4 80 183 5000 18 10 824 5000000000
示例输出 1
3 2 0 1421
对于第一个测试用例,有三个值 x 满足条件: x = 5, 37, 80.
- 当 x=5, f(C, C+5) = f(4,9) = 49 = 7^2
- 当 x=37, f(C, C+37) = f(4,41) = 441 = 21^2
- 当 x=80, f(C, C+80) = f(4,84) = 484 = 22^2
对于第二个测试用例,有两个值 x 满足条件: x = 1, 3133.
- 当 x=1, f(C, C+1) = f(183,184) = 183184 = 428^2
- 当 x=3133, f(C, C+3133) = f(183,3316) = 1833316 = 1354^2
对于第三个测试用例, x 满足条件。
对于第四个测试用例,有 1421 的值 x 满足条件。