题解：AT_abc428_d [ABC428D] 183184

赛时因为精度问题被卡

30

分钟。

分析

考虑把题面里的

f(C,C+x)

表示出来。

设

C+x

的位数为

q

，则有：

f(C,C+x) = C \times 10^q + C + x

因为我们要求得到的这个数是完全平方数，那么可以将其记为

m^2

，其中

m

是正整数：

C \times 10^q + C + x = m^2

整理得：

x = m^2 - (C \times 10^q + C)

因为

x

是有范围的：

1 \le x \le D \\ 10^{q-1} \le C + x \le 10^q - 1 \end{array}\right.$$ 这里记最终得到的 $x$ 的范围是 $[l,r]$，则有： $$l + (C \times 10^q + C) \le m^2 \le r+ (C \times 10^q + C)$$ 此时，将不等式左右两边同时开根号，注意取整问题，解出的 $m$ 的个数就是 $x$ 的个数。 最后，对于每个不同的可能的 $q$，分别计算后相加即可。这里的 $q$ 很小。 **注意 ```double``` 精度问题！** 时间复杂度 $\mathcal{O}(T)$。 --- :::success[[Submission #70267958](https://atcoder.jp/contests/abc428/submissions/70267958)] ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5 + 10; int calc(ll res){ //用于计算数字位数 int cnt = 0; while(res){ cnt ++; res /= 10; } return cnt; } ll qpow(ll x,int p){ ll ans = 1; while(p){ if(p & 1) ans *= x; p >>= 1; x *= x; } return ans; } ll t,c,d; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>t; while(t--){ cin>>c>>d; ll ans = 0; int l = calc(c+1) ,r = calc(c + d); for(int i=l;i<=r;i++){ //枚举 q ll res = c * qpow(10,i) + c; //计算 m^2 的范围 ll a = max(qpow(10,i-1)-c,1ll) + res, b = min(qpow(10,i) - 1 - c,d) + res; long double aa = a , bb = b; //不用 long double 会 WA！ a = ceil(sqrt(aa)); b = floor(sqrt(bb)); ans += b - a + 1; } cout<<ans<<"\n"; } return 0; } ``` :::