题解：P12388 Easy Equation

· · 题解

考虑 i=dx,j=dy,\gcd(x,y)=1，则

\text{popcount}(i+j)\gcd(i,j)=\max(i,j)\to \text{popcount}(dx+dy)=\max(x,y)

发现 \text{popcount}(dx+dy)\le25，所以直接枚举 x,y,d 即可。\ 卡常的话可以钦定 i\le j，减少一半的常数。\ 时间复杂度证明：

\sum_{i=1}^{\log n}\frac{n}{i}\varphi(i)\le\sum_{i=1}^{\log n}\frac{n}{i}\times i=n\log n 
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,c[N],ans;
char cnt[N<<1];//char 是为了卡常，时间可以卡到原来的 1/2
signed main(){
    // freopen("1.in","r",stdin);
    // freopen(".out","w",stdout);
    cin>>n;
    for(int i=1;i<=(n<<1);i++) cnt[i]=cnt[i-(i&-i)]+1;
    for(int i=1;i<=25;i++)
        for(int j=i;j<=25;j++)
            if(__gcd(i,j)==1){
                int k=max(i,j);
                for(int d=k,t=i+j;d<=n;d+=k,t+=i+j)
                    if(cnt[t]==k) c[d]+=1+(i!=j);//i=j 只能算一次
            }
    for(int i=1;i<=n;i++) c[i]+=c[i-1],ans^=c[i];
    cout<<ans<<'\n';
    return 0;
}/*
*/