思路与算法

设a<b，d=gcd(a,b)=a xor b。gcd整除b-a，故b-a≥d；而异或不小于差值，所以d≥b-a，得到d=b-a且a为d的倍数。枚举d及a=d,2d,...,n-d，检查a与d按位与为0；这等价a+d无进位，进而a xor(a+d)=d。计数每个无序对一次。

正确性说明

上述两不等式证明任何合法对都在枚举范围。若a=kd且a&d=0，则b=a+d，gcd(kd,(k+1)d)=d，异或也为d，故接受的一定合法。a固定较小值、d固定差值，因此没有重复。

复杂度

枚举次数Σ(d≤n/2)floor((n-d)/d)=O(nlogn)，每次常数位操作；O(1)额外空间和初始化，计数用64位。n最大10^7。

易错点

a=b时异或0而gcd正，不能计入。两倍数相邻的gcd恒为差值d，是完整性依据。独立大规模答案用按b的SPF因数枚举，而非标程差值枚举。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    long long ans = 0;
    for (int d = 1; d <= n / 2; d++)
        for (int a = d; a <= n - d; a += d)
            if (!(a & d))
                ans++;
    cout << ans << '\n';
}