「UVA12716」GCD等于XOR GCD XOR 解题报告

题面

求范围 $n$ 以内，XOR $=$ GCD 的数的对数，$n\in [1,3\times 10^7]$

即：

$$\sum_{a=1}^n\sum_{b=1}^a[\gcd(a,b)=xor(a,b)]$$

解题思路

数学推理+暴力枚举

说几句闲话

一开始对这道题没什么思路，以为是一个和二进制数有关的 $DP$，猜测复杂度是 $O(n\log n)$，然后就发现貌似自己，哪里推不出来，于是只好点开一个叫做题解的东西

经过三天的思考无果之后，点开题解，结果发现和自己的思路截然不同， 深深地明白自己的弱小

分析

求 $\gcd(a,b)=xor(a,b)$，那么先看看这两个数有什么限制或者联系

首先 $gcd(a,b)\le min(a,b)$，又有 $xor(a,b)$ 的范围挺广的，没有什么限制，看来这样不行

再尝试一下 $a-b(a>=b)$ 和 $xor(a,b)$ 的大小关系，不难发现 $a-b\le xor(a,b)=gcd(a,b)$

由辗转相除法，可知 $a-b\ge xor(a,b)=\gcd(a,b)$

也就说 $a-b=\gcd(a,b)=xor(a,b)$，用 $c$ 表示上式

就有 $a=b+c$，而 $b=kc$ ，所以 $a=(k+1)c$，那么是不是只要枚举 $c$，然后累加上去就好了，这样最后再用前缀和记录一下即可，如果 $c$ 不枚举 $1$，那么实际理论复杂度就是 $O(n\log n)$，和猜的一样

但是，这么简单我还是没有想出来，深深地明白自己的弱小

warning

注意异或的优先级低于等号

Code

#include<bits/stdc++.h>//没有显示结果，Luogu的Romote Judge貌似锅了
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 30000007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n;LL Ans[N+3];
int main()
{
    rint i,j;n=read();
    for(i=1;i<=N;i++) {//很简单的核心代码
        for(j=i;j+i<=N;j+=i)
            if((j^(j+i))==i) ++Ans[j+i];//注意加括号
        Ans[i]+=Ans[i-1];
    }
    for(i=1;i<=n;i++) printf("Case %d: %lld\n",i,Ans[read()]);
    return 0;
}