题解：AT_abc428_d [ABC428D] 183184

· · 题解

在下文中，定义 \text{len}(x) 为 x 的十进制位数，且 c,d 表示题中 C,D。\ 首先 f(c,c+x) 这个形式很难计数，所以考虑把它写成 c\times (10^l+1)+x。（l 为 \text{len}(c+x)）\ 接下来考虑枚举 l（因为 \text{len}(c+d) 可能大于 \text{len}(c)），根据题意易得 \text{len}(c+1)\le l \le \text{len}(c+d)。\ 而因为 c+x 是一个 l 位数，能得出 10^{l-1}\le c+x \le10^l-1 且 1\le x \le d。所以得 \max(1,10^{l-1}-c) \le x \le \min(d,10^l-c-1)。我们得出第一个 x 的范围。\ 接着整合题目中条件。需要 f(c,c+x) 为平方数，即 k^2=x\times (10^l+1)+c 且 \max(1,10^{l-1}-c) \le x \le \min(d,10^l-c-1)。移项一下 k^2=c\times (10^l+1)+x 即得 x=k^2-c\times (10^l+1)，再根据上文的条件并让上下界各加上 c\times (10^l+1) 可以得到求的是 \max(1,10^{l-1}-c)+c\times (10^l+1) \le k^2 \le \min(d,10^l-c-1)+c\times (10^l+1)。方便起见，将上界设为 r，下界设为 l。则可以通过差分思想得 ans=\left\lfloor\sqrt{r}\right\rfloor-\left\lfloor\sqrt{l-1}\right\rfloor。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,d,c;
signed main(){
    cin>>T;
    while(T--){
        cin>>c>>d;
        int ans=0;
        int LL=log10(c+1)+1,RR=log10(c+d)+1;
        for(int i=LL;i<=RR;i++){
            __int128 mul=1;
            for(int j=1;j<=i;j++) mul*=10;
            __int128 lx=max(1ll,(int)(mul/10)-c),rx=min(d,(int)(mul-1-c));
            if(lx>rx) continue;
            __int128 l=c*mul+c+lx,r=c*mul+c+rx,x1=sqrtl(l-1),x2=sqrtl(r);
            ans+=x2-x1;
        }
        cout<<ans<<"\n";
    }
}

如果有公式打错，请私信我。否则求一个赞喵