自动搬运

查看原文

来自洛谷，原作者为

	luanyanjia 菜 -我ら是个と大に傻む逼なり-

搬运于2025-08-24 23:18:16，当前版本为作者最后更新于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$ 得到：

$$x^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 $$

贡献全都是 $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);
}