求修改题解（玄关）

## [Easy Equation](https://www.luogu.com.cn/problem/P12388)

## 解析

因为有 $\gcd$ 在式子中，我们容易想到令：
$$
 k1\times d=i,k2\times d=j
$$
于是原等式两边同时除以 $d$ 可得：
$$
 \operatorname{popcount}((k1+k2)⋅d)=\max(k1,k2)
$$
令 $k1\ge k2$ 可得：
$$
 \operatorname{popcount}((k1+k2)\times d)=k1
$$
**注**：$d=\gcd(i,j)$，$k1⊥k2$。

我们可以枚举 $d,k1,k2$，找到满足上式的值，$k1>k2$ 时**贡献两次**，$k1=k2$ 时**贡献一次**。把得到的贡献记在 $f_{k1\times d}$ 上，最后前缀和加异或。（不要枚举 $i,k1,k2$，时间复杂度会多一个 $\log$，~~比赛时我就这么超时的。~~）

**优化**：

1. 预处理 $\operatorname{popcount}(1\sim20000000)$ 的值。
2. 不难发现 $\operatorname{popcount}((k1+k2)\times d)$ 不大于 $\log(2 \times 10^7)$，即 $k1,k2$ 不大于 $25$。

---

[AC](https://www.luogu.com.cn/record/215730471) 记录。

---

## 代码

```cpp
#include <bits/stdc++.h>
using namespace std;

#define lowbit(x) (x&(~x+1))

const int N=40,mx=25,N2=1e7+10;

int n;
long long ans;
bool st[N][N];//判断互质的数。
long long sum[N2];//贡献和。
int pop[N2<<1];//二进制下数中1的个数。

int gcd(int a,int b){//最大公因数。
	return b==0?a:gcd(b,a%b);
}

void prework(){
  //预处理二进制下数中1的个数。
	for(int i=1;i<=(N2-10)<<1;i++){
		pop[i]=pop[i-lowbit(i)]+1;
	}
  //预处理互质的数。
	for(int i=1;i<=25;i++){
		for(int j=1;j<=i;j++){
			if(gcd(i,j)==1){
				st[i][j]=true;
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	prework();
  //枚举d，k1，k2。
	for(int d=1;d<=n;d++){
		for(int i=1;i<=min(25,n/d);i++){
			for(int j=1;j<=i;j++){
				if(pop[i*d+j*d]==i && st[i][j]){
					if(i!=j)sum[i*d]+=2;
					else sum[i*d]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		sum[i]+=sum[i-1];//前缀和。
		ans^=sum[i];//异或记入答案。
	}
	cout<<ans;
	return 0;
}