题目链接： https://vjudge.net/problem/UVA-12716
题目描述： 给你一个N， 让你求1~N内所有的GCD(A，B) == A XOR B的个数， 其中1 <= B <= A <= N , N <= 3e7
解题思路： gcd(a, b) = a ^ b = c, 异或的性质是a ^ b = c 则 a ^ c = b 所以我们就枚举a, c得出b , 此时如果gcd(a, b) == c则++ans, 枚举a是O(n)， 枚举因数模仿素数筛法枚举a, c是O(nlogn), 判断gcd是logn所以是O(nlognlogn), 这里N是3e7照理说是不会T了， 但是确实是T了， 可能是这个方法卡常， 这里我们还有O(nlogn)的做法， 这样是不会T的， 由于异或是不进位的加法， 所以a - b <= a ^ b 相等的时候是a == b ， 同时a - b >= c 由于a ^ b == c 所以说a-b>=c && a-b<=所以a-b==c ， 所以这里我们就能O(1)得出b, 再O(1)判断a^b是否==c这样复杂度就能降下来了， 题目就可以A了
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,0x3f,sizeof(a)) #define fi(n) for(i=0;i<n;i++) #define fj(m) for(j=0;j<m;j++) #define sca(x) scanf("%d",&x) #define scalld(x) scanf("%I64d",&x) #define print(x) printf("%d ",x) #define printlld(x) printf("%I64d ",x) #define d printf("======= ") typedef long long ll; using namespace std; const int maxn = 3e7; ll ans[maxn+10]; ll gcd( ll a, ll b ) { return( b == 0 ? a : gcd( b, a%b ) ); } void build() { mem0(ans); int n = maxn >> 1; for( int c = 1; c <= n; c++ ) { for( int a = 2*c; a <= maxn; a+=c ) { ll b = a ^ c; // TLE!!!!!!!!!!!!!!!! if( a >= b && gcd(a, b) == c ) ++ans[a]; // ll b = a-c; // if( (a ^ b) == c ) ++ans[a]; } } // for( int i = 1; i <= 10; i++ ) { // cout << ans[i] << " "; // } // cout << endl; for( int i = 2; i <= maxn; i++ ) { ans[i] += ans[i-1]; } } int main() { int t; // cout << gcd(9,15) << endl; build(); sca(t); int cases = 1; while( t-- ) { ll res = 0; int n; sca(n); res = ans[n]; printf( "Case %d: %lld ", cases++, res ); } return 0; }
思考 ： 数论真的是好神奇啊， 对数字的敏感性要求是真的高， 而且这个东西得自己动脑筋去想才能够解题， 同时还要掌握更多的定理来支持自己， 一会儿hihocoder啦， 激动ing......