题解：AT_abc428_d [ABC428D] 183184
__FL__
·
·
题解
AT_abc428_d [ABC428D] 183184
小清新思维题。
Solution
看到这个题一般都会想到去枚举完全平方数，然而 f(C,C+x) 最大可以达到 2\times 10^{18} 量级，不可行。
我们不妨换一个思路，注意到在钦定了 C+x 的位数 k 的前提下，f(C,C+x) 能表示的是一个连续的范围。设 L,R 分别为这个范围的上界和下界，则有：
L=\max(C\times 10^k+10^{k-1},C\times 10^k+C+1)
R=\min[(C+1)\times 10^k-1,C\times 10^k+C+D]
易证对于一段连续的区间 $L,R$，若 $l^2,r^2\ (l,r\ge0)$ 都在这段区间内，则对任意 $l\le i\le r$，$i^2$ 都在这段区间内。令 $l,r$ 分别为能使它的平方被区间包含的最小值/最大值，则有：
$$l=\left \lceil \sqrt{L} \right \rceil,r=\left \lfloor \sqrt{R} \right \rfloor $$
枚举 $k$，累加 $r-l+1$。
注意可能需要额外注意数据溢出的问题。
## Code
```cpp
#include<bits/stdc++.h>
#define int long long
#define ull unsigned int
using namespace std;
const int N = 200005;
ull t,c,d;
ull pw[N];
int p10(ull a)
{
int ret = 0;
while (a) ret++,a /= 10;
return ret;
}
signed main()
{
ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
pw[0] = 1;
for (int i = 1; i <= 18; i++)
pw[i] = pw[i-1]*10;
cin >> t;
while (t--)
{
cin >> c >> d;
int ans = 0;
for (int i = p10(c+1); i; i++)
{
ull l = c*pw[i]+max(pw[i-1],c+1),r = min((c+1)*pw[i]-1,c*pw[i]+c+d);
if (l > r) break;
ull beg = (int)sqrtl(l-1)+1,las = sqrtl(r);
if (beg > las) continue;
ans += las-beg+1;
if (p10(r) >= 19) break;
}
cout << ans << '\n';
}
return 0;
}
```