首先没看懂XOR(于是百度了一下):异或,英文为exclusive OR,或缩写成xor。同时还有一个OR,于是一起看了一眼:
大意:
输入一个整数n,在1~n内,有多少对整数(a,b)满足GCD(a,b)== a XOR b。
看着这个脑中闪过暴力,因为 a ^ b = c, 则 a ^ c = b,所以直接枚举a和c就好,然后算出 b = a ^ c,最后 if ( GCD( a, b) == c )就好。
后来看了一下大佬的博客发现还有更简便的做法。
于是乎自己敲了一份:
1 #include2 const int MAX = 30000005; 3 int ans[MAX]; 4 5 void pre() 6 { 7 for (int i = 1; i < MAX; i++) // i 即 a - b 8 { 9 for (int j = i + i; j < MAX; j += i) // j 即 a10 if ((j ^ (j - i)) == i) // 判断是否有 a ^ b == a - b11 ans[j] ++;12 ans[i] += ans[i - 1];13 }14 }15 16 int main()17 {18 pre(); //打表即可19 int t;20 scanf("%d", &t);21 for (int i = 1; i <= t; i++)22 {23 int n;24 scanf("%d", &n);25 printf("Case %d: %d\n", i, ans[n]);26 }27 return 0;28 }