专栏文章

AT_abc428_d 题解

MMoya_Rao啾？啾！
AT_abc428_d题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minkfe2w
此快照首次捕获于
2025/12/02 03:52
3 个月前
此快照最后确认于
2025/12/02 03:52
3 个月前
查看原文
如果你比赛的时候调了半年没调出来，赛后发现是二分的边界设小了，你也会崩溃的，相信我。
观察这个 ff 的定义，发现如果给定的是 f(x,y)f(x,y) 且 xx 固定的话，yy 的位数会直接影响整个的结果。因为，假设 yy 的位数为 lyly，那么这里的值就是 x×10ly+yx \times 10^{ly} + y。很显然，虽然 xx 固定，但是它后面乘的那个 10ly10^{ly} 是根据 lyly 的具体值在不断变化的。
然后由于 c+dc+d 的这个范围也就个 6×1096 \times 10^9 的一个级别，不大，因此可以枚举这个位数 lyly，这里简单记为 ii。
考虑在固定了位数 ii 之后，你的这个值的取值范围在一个怎样的趋势。
不难发现 L=c×10i+max⁡(c+1,10i−1)L = c \times 10^i + \max(c+1,10^{i-1})。前面那个 c×10ic \times 10^i 我倒能理解，可这个 max⁡(c+1,10i−1)\max(c+1,10^{i-1}) 是什么东西啊喂？想想吧！如果这里要有 ii 位，至少也要有 10i−110^{i-1} 次方，这是最小的 ii 位数了，不然根本不可能有 ii 位啊！换句话说，如果 c=183c=183 且 i=3i=3 的话，像 183009183009、183047183047 这种是不会算进去的。至于和 c+1c+1 取 max⁡\max，问我 c+1c+1 是什么，题目中说了那个数的取值范围，至少为 11，因此在这里至少也是 c+1c+1 咯。
LL 求完了，RR 呢？同样可得出 R=min⁡((c+1)×10i−1,c×10i+c+d)R = \min( (c+1) \times 10^i -1 , c \times 10^i + c + d )。(c+1)×10i−1(c+1) \times 10^i - 1 很好理解，就是当前面的前缀不为 cc 了之后肯定就不算了，那么当 c=183c=183 且 i=3i=3 的时候这个右边界就是 183999183999；但是对 c×10i+c+dc \times 10^i + c + d 取 min⁡\min 又是个什么东西呢？因为题目给定的最大是 dd，加上 cc，这个算出来的值已经是最大上界了，你不可能比这个还多呀！还多，那也取不到一个 ≤d\le d 的数字了。
算出 LL 和 RR 之后，就可以开始算了。这边采用的二分，好像也可以开根。算出 [L,R][L,R] 这个范围内有多少个完全平方数，加进答案里就行。
最后提一嘴 ii 的枚举范围，很显然，最小是 c+1c+1 的位数，最大是 c+dc+d 的位数。
具体实现上，我弄了两个函数，Lth(x)Lth(x) 用于算出 xx 的位数，而 Mth(x)Mth(x) 则返回 10x10^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;
}
如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...