题解：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]

#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;
}

:::