题解：AT_abc428_d [ABC428D] 183184

ABC428D

Solution

写出式子：$(10^k+1)\times C + x = m^2$。

首先要想想答案该怎么求，很明显枚举 $x$ 不现实，要从 $m$ 入手。
但是想想枚举 $m$ 还是不行，因为 $t\le 3\times 10^5$，单次复杂度要小于 $100$ 才行。
和我一样数学不好的是肯定看不出明显结论的，但是还可以枚举一个位数。

对于 $C+x$，最小的位数肯定是 $C+1$ 的位数，最大的就是 $C+D$ 的位数。
这里提供一个求 $k$ 的位数的快速方法：

len=to_string(k).size();

然后用 $i$ 枚举一下这个位数：

求出此时 $x$ 的最小和最大值 $a,b$。
求出对于 $x=a,x=b$ 时的最终结果 $A,B$。
找到 $\min(p)$ 且 $p^2\ge A$，和 $\max(q)$ 且 $q^2\le B$。
对于任何在 $p,q$ 之间的数一定也能作为 $m$，所以答案加上 $q-p+1$。

Code

#include<bits/stdc++.h>
using namespace std;
using LL=long long;

LL p[18]={1};

LL sq(LL n){
    if(n==0)return 0;
    LL l=1,r=n;
    while(l<r){
        LL m=(l+r+1)/2;
        if(m<=n/m)l=m;
        else r=m-1;
    }
    return l;
}

void solve(){
    LL c,d;
    cin>>c>>d;
    LL ans=0;
    LL mn=c+1,mx=c+d;
    int l1=to_string(mn).size(),l2=to_string(mx).size();
    for(int i=l1;i<=l2;i++){
        LL a=max(1LL,p[i-1]-c);
        LL b=min(d,p[i]-1-c);
        if(a>b)continue;
        LL A=c*p[i]+(c+a);
        LL B=c*p[i]+(c+b);
        LL x=sq(A);
        if(x*x<A)x++;
        LL y=sq(B);
        if(x<=y)ans+=y-x+1;
    }
    cout<<ans<<"\n";
}

int main(){
    for(int i=1;i<=17;i++)p[i]=p[i-1]*10;
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}