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

luanyanjia · 2025-06-14 18:27:00 · 题解

神秘复杂度水过了。

先来看这个 x \oplus y = \gcd(x,y)，也就是 x \oplus \gcd(x,y) = y，我们发现对于一个 d，x \oplus d \le x + d。但是 y > x 所以 y 至少是 x + d，因此 y = x + d，此时若 d \mid x，则一定有 \gcd(x,y) = d。

在看这个神秘的一看就是凑出来的条件，将 y 换成 x + d，x 换成 a \times d 得到：

贡献全都是 d^2，问题变成对每个 d 求有多少个 x 使得 d \mid x \land d \operatorname{and} x = 0，其中 \operatorname{and} 是按位与。

我想过先 O(3^{\log_2m}) 枚举后面几位，但是由于我不会数论，所以后面不会 O(1) 求就有点寄，所以可以考虑一些神秘的暴力。

显然有直接暴力，对于一个 d 是 O(\dfrac{n}{d}) 的。

然后 d 小的时候可以发现后面几位是有周期的，就可以记一下最后几位每一个状态是否被访问过，如果出现周期直接计算即可。复杂度 O(d)。

合起来就是 \sum\limits_{i=1}^m{\min(i,\dfrac{n}{i})}。居然可以通过。虽然 n 再大一点就直接死了。

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);
}