自动搬运

查看原文

来自洛谷，原作者为

	lichengyun 这个家伙是个废物

搬运于2025-08-24 22:35:10，当前版本为作者最后更新于2022-07-02 16:53:03，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到没人发题解，就来水一发（doge)

P8015题目

题意翻译：有k个真分数集 $S_1 , S_2 , \ldots , S_n$ ，

式中，对 $\forall i(i \in [1,n] )$ 都有 $S_i= \lbrace \frac{1}{i} , \frac{2}{i} , \ldots , \frac{n-1}{i} \rbrace$。

求 $|S_1 \cup S_2 \cup \ldots S_n|$。

解法：考虑对每一个分数，都将其简化为既约分数。对于一个给定的整数 $x (x > 1)$，共有 $φ(i)$ 个既约真分数以 $x$ 为分母。

又对于一个给定的分数，显然有且仅有一个既约分数等于原数。

于是我们这就得到了本题的正解！

枚举每一个 $A_i$ 的约数集合。对于不同集合中的相同约数 $d_j$，只计算其贡献 $φ(d_j)$ 一次。

代码：

#include <bits/stdc++.h>
using namespace std;
bool v[1919810];
bool vis[314514];
int pr[29999],phi[314514],ptr=0;
int euler(int n){//线筛，筛phi函数
	memset(v,1,sizeof(v));
	v[0]=v[1]=false;
	for(int i=2;i<=n;i++){
		if(v[i]){
			pr[ptr++]=i;
			phi[i]=i-1;
		}
		for(int j=0;j<=ptr && (pr[j]*i<n);j++){
			v[i*pr[j]]=false;
			phi[i*pr[j]]=phi[i]*phi[pr[j]];
			if(i%pr[j]==0){
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
		}
	}
	return 0;
}
int main(int argc,char *argv[]){
	ios::sync_with_stdio(0);
	euler(131072);
	int n,ans=0;cin>>n;n++;
	while(n--){
		int A;cin>>A;//每次处理一个数
		for(int i=1;i*i<=A;i++){
			if(A%i==0){
				int j=A/i;
				//判重+算贡献
				ans+=(1-vis[i])*phi[i];vis[i]=1;
				ans+=(1-vis[j])*phi[j];vis[j]=1;
				cout<<i<<' '<<j<<'\n';
			}
		}
	}
	
	cout<<ans;
	return 0;
}