神秘啊
\(x\oplus y=gcd(x,y)\)
发现，当 \(x<y\) 时，\(x\oplus y\ge y-x\ge gcd(x,y)\)
那么我们这个条件就限定了上面这 \(3\) 个东西相等，记为 \(d\)
\(y-x=d\) 且 \(gcd(x,y)=d\)
那么设 \(x=kd\)，\(y=kd+d\)
\(k^{2}d^{2}\mod kd^{2}+d^{2}\)
\(d^{2}(k^{2}\mod k+1)\)
\(d^{2}(1+(k+1)(k-1)\mod k+1)\)
\(d^{2}\)
那么我们现在把条件变成了
我们找到一个x，然后找到它二进制的子集作为 \(d\)，这样的话，我们也能找到 \(y=x-d\)，现在我们要统计 \(d^{2}\) 的和。不兑，我们还有一个 \(gcd\) 的限制
那么我们枚举 \(x\)，然后看看二进制最大的后缀使得 \(\le x\)，然后加上 \(d^2\)，这样是 \(x\log m\) 的，实现优秀可以获得 \(50\) 分。
我们不妨对于所有符合条件的后缀二进制计数。枚举 \(d\)，求有多少 \(y\) 使得 \(d|y\) 并且 \(d\) 二进制下为 \(y\) 的真子集。
也就是说 \(y\equiv 0\pmod d\) 且 \(y\equiv d\pmod {2^{k}}\) 其中 \(2^{k}\) 为 \(\ge d\) 的第一个二次幂
这样是不足以刻画这个条件的？我唐了，原来 \(y\) 是 \(d\) 的超集。那么我们先枚举 \(y\) 后面 \(\log m\) 位，然后枚举子集作为 \(d\)，然后得到一个方程组 \(y\equiv 0\pmod d\) 且 \(y\equiv p\pmod {2^{k}}\) 其中 \(2^{k}\) 为 \(\ge d\) 的第一个二次幂，这样就好了。
枚举子集，思想很简单，比如我们要枚举 \(x\) 的子集，我们首先扔到 \(for\) 循环里，然后每次 \(-1\)，再和 \(x\) 取个交即可
这题我们是枚举超集，一样的
复习一下 \(\text{excrt}\)
现在我们考虑合并
\(x\equiv a_{1}\pmod {b_{1}}\)
\(x\equiv a_{2}\pmod {b_{2}}\)
首先，我们新方程的模数是 \(lcm(b_{1},b_{2})\) 这个容易理解
\(x=a_{1}+k_{1}b_{1}\)
\(x=a_{2}+k_{2}b_{2}\)
\(k_{1}b_{1}-k_{2}b_{2}=a_{2}-a_{1}\)
使用 \(exgcd\)，求出来了 \(k1\) 和 \(k2\)，此时我们也知道了 \(x\)，因为我们又知道了新的模数，所以我们直接让 \(x\) 对新的模数取模即可，这样就是 \(excrt\) 了！看起来之前学得还不错