本文共 666 字，大约阅读时间需要 2 分钟。
求
∑ a = 1 n ∑ b = 1 a ( g c d ( a , b ) = = a x o r b ) \sum_{a=1}^n\sum_{b=1}^a(gcd(a,b)==a\ xor\ b) a=1∑nb=1∑a(gcd(a,b)==a xor b)因为 a = = b a==b a==b时肯定不成立，所以直接计算 a > b a>b a>b
那么 g c d ( a , b ) ⩽ a − b gcd(a,b)\leqslant a-b gcd(a,b)⩽a−b， a x o r b ⩾ a − b a\ xor\ b\geqslant a-b a xor b⩾a−b 我们设 c = a − b c=a-b c=a−b，然后枚举一个 c c c和一个 i i i, a = c ∗ i a=c*i a=c∗i，因为 g c d ( a , a − c ) = c gcd(a,a-c)=c gcd(a,a−c)=c，所以只需要判断 a − c = a x o r c a-c=a\ xor\ c a−c=a xor c就好了#includeusing namespace std;int n,s;int main(){ scanf("%d",&n); for(int i=1;i<=n/2;i++) for(int j=i*2;j<=n;j+=i) if((i^j)==j-i) s++; printf("%d",s);}
转载地址：http://jxzaf.baihongyu.com/