【数论】SSL

题意

求出$1\sim N$中有多少个无序数对$(a,b)$的$gcd(a,b)=axorb。$

思路

设$c=gcd(a,b)=axorb$ $\because axorb=c$ $\therefore axorc=b$ $\therefore gcd(a,axorc)=gcd(a,b)=axorb=c$ $\because gcd(a,b)\le a-b,axorb\ge a-b$ $\therefore c=a-b$ $\therefore b=a-c$ $\therefore gcd(a,a-c)=gcd(a,b)=c$ $\because gcd(a,axorc)=c$ $\therefore axorc=a-c$ 由设中我们知道$c$为$a$的约数，所以枚举$c$再找出它的倍数$a$。

代码

#include<cstdio> #include<algorithm> using namespace std; int N, ans; int main() { scanf("%d", &N); for (int i = 1; i <= N / 2; i++) for (int j = i * 2; j <= N; j += i) if ((j - i) == (i ^ j)) ans++; printf("%d", ans); }