自动搬运

查看原文

来自洛谷，原作者为

	CQ_Bab 行稳致远

搬运于2025-08-24 23:15:10，当前版本为作者最后更新于2025-06-05 12:31:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

我们考虑化柿子，首先我们可以设 $\gcd(x,y)=d$ 那么我们把 $x=d\times a,y=d\times b$ 然后柿子就变成了 $pc(d\times (a+b))\times d=\max(a,b)\times d$ 然后又变成了 $pc(d\times(a+b))=\max(a,b)$ 那么我们有考虑一下左边这坨柿子的最大值，我们发现最大值能取 $22$ 然后我们枚举的 $a,b$ 都最大是 $22$ 然后我们考虑暴力枚举 $a,b$ 并且要保证 $\gcd(a,b)=1$ 然后我们暴力枚举 $d$ 即可，再看是否合法，如果合法我们发现 $\max(a,b)\times d$ 就为这对值能取到的第一个值，然后我们在用前缀和求出每一个点的准确值即可。

代码

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
//#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') {ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
}
int T=1;
int n;
const int N=1e7+10;
int a[N],f[N]; 
int cc[N*2];
vector<int>v[30];
int vis[30][30];
void solve() {
	in(n);
	rep(i,1,n*2) cc[i]=cc[i/2]+(i&1);
	rep(a,1,22) {
		rep(b,a,22) {
			if(__gcd(a,b)==1) {
				if(a==b) v[a].pb(b);
				else v[b].pb(a);
			}
		}
	}
	rep(a,1,22) {
		for(auto b:v[a]) {
			int tt=0;
			rep(k,1,n/max(a,b)) {
				if(cc[(a+b)*k]==max(a,b)) {
					if(a!=b) f[max(a*k,b*k)]+=2;
					else f[a*k]++;
				}
			}
		}
	}
	int res=0;
	rep(i,1,n) f[i]+=f[i-1],res^=f[i];
	print(res);
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}

要卡下常。