UVA - 12716 - 异或序列
求满足GCD(a,b) = a XOR b; 其中1<=b <=a<=n。
首先做这道题需要知道几个定理：
异或：a XOR b = c 那么 a XOR c = b;
那么我们令GCD（a,b）= c; 这样 a 是 c 倍数。我们可以通过遍历c , 然后通过筛法，把c的倍数晒出当作a。求b如何求呢？
书上提供一种方法是利用a XOR c=b 用 gcd(a,b)=c 验证。但是这个方法是超时的，gcd是logn 级别的 总的时间复杂度，n*(logn)^2。这是我们不能接受的。
还有一种方法是证明b=a-c。这个证明还是不容易的 :
首先gcd(a,b)=c<=a-b 其次要证明a^b>=a-b 但是这是不容易。我们可以这样想，他们什么时候取等于，我们知道异或是相同为0，不同为1 那么 我们把a,b用二进制展开，这样我们a,b是每一位对应的，我们把所以不同的二进制位，全部变为ai = 1，bi = 0。这样我们知道，没有借位 那么a^b == a-b 。那么后面按照XOR序列的顺序变化，a-b变小，那么a^b>=a-b 从而 c=a-b。命题得证。
证明是否成立，直接用a^b==a-b即可。可以的把，保持在f数组里面，f[i]代表a=i时的情况数。最后求一个前缀和既可以，最后o1查找即可。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define rep(i,j,k) for(int i=j;i<=k;i++) using namespace std; const int maxx=30000001; int f[maxx]; void init(){ for (int i=1;i<=maxx/2;i++){ for (int j=2*i;j<=maxx;j+=i){ int b=j-i; if ((j^b)==i){ f[j]++; } } } for (int i=2;i<=maxx;i++){ f[i]+=f[i-1]; } } int main(){ int t; int n; int zz=0; scanf("%d",&t); int cnt=0; int a; memset(f,0,sizeof(f)); init(); while(t--){ zz++; scanf("%d",&n); printf("Case %d: %d\n",zz,f[n]); } return 0; }
