题解：P12388 Easy Equation

Easy Equation

解析

因为有

\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

，~~比赛时我就这么超时的。~~）

优化：

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

AC 记录。

代码

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;
}

题解：P12388 Easy Equation

文章操作

Easy Equation

解析

代码

相关推荐

评论

题解：P12388 Easy Equation