专栏文章

P12828 「DLESS-2」XOR and Number Theory 题解

lluanyanjia
P12828题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@mip3bllv
此快照首次捕获于
2025/12/03 05:28
3 个月前
此快照最后确认于
2025/12/03 05:28
3 个月前
查看原文
神秘复杂度水过了。
先来看这个 x⊕y=gcd⁡(x,y)x \oplus y = \gcd(x,y)，也就是 x⊕gcd⁡(x,y)=yx \oplus \gcd(x,y) = y，我们发现对于一个 dd，x⊕d≤x+dx \oplus d \le x + d。但是 y>xy > x 所以 yy 至少是 x+dx + d，因此 y=x+dy = x + d，此时若 d∣xd \mid x，则一定有 gcd⁡(x,y)=d\gcd(x,y) = d。
在看这个神秘的一看就是凑出来的条件，将 yy 换成 x+dx + d，xx 换成 a×da \times d 得到：
x2 mod (y2−xy)=x2 mod (x2+2xd+d2−x2−xd)=x2 mod d(d+x)=a2d2 mod d2(a+1)=d2(a2 mod (a+1))=d2x^2 \bmod (y^2 - xy) \\ = x^2 \bmod (x^2 + 2xd + d^2 - x^2 -xd) \\ = x^2 \bmod d(d+x) \\ = a^2d^2 \bmod d^2(a+1) \\ = d^2(a^2 \bmod (a+1)) \\ = d^2
贡献全都是 d2d^2，问题变成对每个 dd 求有多少个 xx 使得 d∣x∧dand⁡x=0d \mid x \land d \operatorname{and} x = 0，其中 and⁡\operatorname{and} 是按位与。
我想过先 O(3log⁡2m)O(3^{\log_2m}) 枚举后面几位，但是由于我不会数论，所以后面不会 O(1)O(1) 求就有点寄，所以可以考虑一些神秘的暴力。
显然有直接暴力，对于一个 dd 是 O(nd)O(\dfrac{n}{d}) 的。
然后 dd 小的时候可以发现后面几位是有周期的，就可以记一下最后几位每一个状态是否被访问过，如果出现周期直接计算即可。复杂度 O(d)O(d)。
合起来就是 ∑i=1mmin⁡(i,ni)\sum\limits_{i=1}^m{\min(i,\dfrac{n}{i})}。居然可以通过。虽然 nn 再大一点就直接死了。
CPP
inline void Solve(){
    rd(n,m);
    int ans=0;
    for(int d=1;d<B&&d<=m;d++){
        bt.reset();
        int cnt=0;
        for(int i=d,c=1;i+d<=n;i+=d,++c){
            int k=i&(B-1);
            if(bt[k]){
                --c;
                cnt+=((n-d)/d/c-1)*s[c]+s[((n-d)/d)%c];
                break;
            }
            bt[k]=1;
            s[c]=s[c-1];
            if((i&d)==0)++cnt,++s[c];
        }
        Add(ans,1ll*cnt*d%mod*d%mod);
    }
    for(int d=B;d<=m;d++){
        int cnt=0;
        for(int i=d;i+d<=n;i+=d)
            if((i&d)==0)++cnt;
        Add(ans,1ll*cnt*d%mod*d%mod);
    }
    printf("%d\n",ans);
}

评论

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

正在加载评论...