AT_abc428_d 题解
Moya_Rao
·
·
题解
如果你比赛的时候调了半年没调出来，赛后发现是二分的边界设小了，你也会崩溃的，相信我。
观察这个 f 的定义，发现如果给定的是 f(x,y) 且 x 固定的话，y 的位数会直接影响整个的结果。因为，假设 y 的位数为 ly，那么这里的值就是 x \times 10^{ly} + y。很显然，虽然 x 固定，但是它后面乘的那个 10^{ly} 是根据 ly 的具体值在不断变化的。
然后由于 c+d 的这个范围也就个 6 \times 10^9 的一个级别，不大，因此可以枚举这个位数 ly，这里简单记为 i。
考虑在固定了位数 i 之后，你的这个值的取值范围在一个怎样的趋势。
不难发现 L = c \times 10^i + \max(c+1,10^{i-1})。前面那个 c \times 10^i 我倒能理解，可这个 \max(c+1,10^{i-1}) 是什么东西啊喂？想想吧！如果这里要有 i 位，至少也要有 10^{i-1} 次方，这是最小的 i 位数了，不然根本不可能有 i 位啊！换句话说，如果 c=183 且 i=3 的话，像 183009、183047 这种是不会算进去的。至于和 c+1 取 \max，问我 c+1 是什么，题目中说了那个数的取值范围，至少为 1，因此在这里至少也是 c+1 咯。
算出 $L$ 和 $R$ 之后，就可以开始算了。这边采用的二分，好像也可以开根。算出 $[L,R]$ 这个范围内有多少个完全平方数，加进答案里就行。
最后提一嘴 $i$ 的枚举范围，很显然，最小是 $c+1$ 的位数，最大是 $c+d$ 的位数。
具体实现上，我弄了两个函数，$Lth(x)$ 用于算出 $x$ 的位数，而 $Mth(x)$ 则返回 $10^x$。
```cpp
#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define fr first
#define se second
#define pb push_back
using namespace std;
LL T,c,d,St,Ed,Ans;
LL read(){
LL su=0,pp=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
return su*pp;
}
LL Lth(LL x){
LL cnt=0;
while(x)cnt++,x/=10;
return cnt;
}
LL Mth(LL h){
LL x=1;
while(h--)x*=10;
return x;
}
LL Fd(LL D){
LL l=1,r=3000000000,res=0;
//这里一定一定一定要开到 3e9 啊！（2e9 疑似也可以，但是不严谨
//我赛时开的 1e9 愣是卡得我 WA *2 呜呜呜呜呜呜
while(l<=r){
LL mid=(l+r)/2;
LL x=mid*mid;
if(x<=D)res=mid,l=mid+1;
else r=mid-1;
}return res;
}
int main(){
T=read();
while(T--){
c=read(),d=read();
St=Lth(c+1),Ed=Lth(d+c),Ans=0;
for(LL i=St;i<=Ed;i++){
LL L=c*Mth(i)+max(c+1,Mth(i-1));
LL R=min((c+1)*Mth(i)-1,c*Mth(i)+c+d);
if(L<=R)Ans+=Fd(R)-Fd(L-1);
}cout<<Ans<<"\n";
}
return 0;
}
```
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！