【JZOJ4714】公约数【数论，数学】

题目大意：

题目链接：https://jzoj.net/senior/#main/show/4714 题目图片： http://wx4.sinaimg.cn/mw690/0060lm7Tly1fwp1egqfr7j30j70gkglv.jpg 给定一个正整数$n$，求在$[1,n]$的范围内，有多少个无序数对$(a,b)$满足$gcd(a,b)=axorb$。

---

思路：

令$c=gcd(a,b)=axorb$，证明满足$gcd(a,b)=axorb$必有$a-c=axorc$ $$证明过程$$ 还是比较好理解的。同学写了证明过程↑，可以直接进去。 所以就枚举$c$，由于$c$是$a$的一个因数（$gcd(a,b)=c$中可以得出），所以再枚举$ck=a$然后判断即可。

---

代码：

#include <cstdio> #define R register using namespace std; int n,sum; int main() { scanf("%d",&n); for (R int c=1;c<=n;c++) for (R int i=2;c*i<=n;i++) { int a=c*i; if (a-c==(a^c)) sum++; } printf("%d\n",sum); return 0; }