自动搬运

查看原文

来自洛谷，原作者为

	whiteqwq 寻找着梦与现实的交点 在哪呢 在哪呢

搬运于2025-08-24 22:05:23，当前版本为作者最后更新于2021-03-22 13:41:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P4930 [PA2013]Euler解题报告：

更好的阅读体验

题意

$T$组数据，给定$n$，求$\varphi(m)=n$的所有$m$。（$1\leqslant n\leqslant 10^{10}$）

分析

原来的题目数据有锅，修完数据后拿到了首杀。

搜索题。

首先$O(\sqrt{n})$求出$n$的所有因子计入$D_{1\cdots Ds}$，然后把所有$D_i+1$中为质数的值存入$P_{1\cdots Ps}$，不难发现$Ds$和$Ps$很小，随便交几发讨论一下就可以知道$Ds$最大是$2500$，$Ps$最大是$700$。

记$ord_i$为数字$i$在$n$质因数中的排名，但由于这里可能存不下，因此考虑对于$i$的大小讨论：如果$i\leqslant \sqrt{n}$则将$i$的排名存入$ord_i$，否则将$i$的排名存入$nord_{\frac{n}{i}}$，这样就只需要开$O(\sqrt{n})$的数组了。

然后就开始玄学起来了。

设$f_{i,j}$代表$P_j\cdots P_{Ps}$中第一个是$D_i$因子的数的编号，（如果不存在则为$Ps+1$）

这里介绍一个众所周知的结论：对于$n=\prod_{i=1}^s p_i^k$，满足$\varphi(n)=n\times\prod_{i=1}^s\frac{p_i-1}{p_i}$（下面有证明）。

然后进行搜索：$dfs(pos,val,now)$表示现在搜索到第$pos$个$P$了，将$n$除到了$now$（这个$now$为值），并把答案乘到了$val$，边界就是$now=1$的时候直接把$val$放入答案。

不难发现$now$一定在$D$里（可以通过$ord$和$nord$找到），因此我们可以通过$f$跳过那些不能整除$now$的$P$。

然后再分类讨论就好了：

• 与当前质数无关系，直接$dfs(pos+1,val,now)$。
• 只有$1$次幂，把$now$除去$P_{pos}-1$，把$val$乘上$P_{pos}$，然后$dfs(pos+1,val,now)$。
• 有高次幂，那么在$1$次幂的基础上将$now$除去若干次$P_pos$，把$val$乘上若干次$P_{pos}$，然后$dfs(pos+1,val,now)$。

复杂度很玄学，但跑的很稳。

代码

记得特判$n=1$，还有有些地方需要排序。

#include<stdio.h>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=1000005,maxm=2505,maxk=700;
int T,n,cnt,m,Ps,Ds,anss;
int p[maxn],a[maxn],P[maxk],D[maxm],ans[maxn],ord[maxn],nord[maxn],f[maxm][maxk];
void sieve(int n){
	for(int i=2;i<=n;i++){
		if(p[i]==0)
			a[++cnt]=i;
		for(int j=1;j<=cnt;j++){
			if(i*a[j]>n)
				break;
			p[i*a[j]]=1;
			if(i%a[j]==0)
				break;
		}
	}
}
int check(int x){
	if(x<=1000000)
		return p[x]==0;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
			return 0;
	return 1;
}
void dfs(int pos,int val,int now){
	if(now==1){
		ans[++anss]=val;
		return ;
	}
	if(now<=m)
		pos=f[ord[now]][pos];
	else pos=f[nord[n/now]][pos];
	if(pos==Ps+1)
		return ;
	dfs(pos+1,val,now);
	val*=P[pos],now/=P[pos]-1,dfs(pos+1,val,now);
	while(now%P[pos]==0)
		val*=P[pos],now/=P[pos],dfs(pos+1,val,now);
}
signed main(){
	scanf("%lld",&T),sieve(1000000);
	while(T--){
		scanf("%lld",&n);
		if(n==1){
			puts("2\n1 2");
			continue;
		}
		for(m=1;1ll*(m+1)*(m+1)<=n;m++);
		for(int i=1;i<=m;i++)
			if(n%i==0){
				D[++Ds]=i;
				if(check(i+1))
					P[++Ps]=i+1;
				if(1ll*i*i!=n){
					D[++Ds]=n/i;
					if(check(n/i+1))
						P[++Ps]=n/i+1;
				}
			}
		sort(P+1,P+1+Ps),sort(D+1,D+1+Ds);
		for(int i=1;i<=Ds;i++){
			if(D[i]<=m)
				ord[D[i]]=i;
			else nord[n/D[i]]=i;
			f[i][Ps+1]=Ps+1;
			for(int j=Ps;j>=0;j--)
				f[i][j]=D[i]%(P[j]-1)==0? j:f[i][j+1];
		}
		dfs(1,1,n),sort(ans+1,ans+1+anss);
		printf("%lld\n",anss);
		for(int i=1;i<=anss;i++)
			printf("%lld%c",ans[i],i==anss? '\n':' ');
		if(anss==0)
			puts("");
		for(int i=1;i<=Ds;i++){
			if(D[i]<=m)
				ord[D[i]]=0;
			else nord[n/D[i]]=0;
		}
		anss=Ds=Ps=0;
	}
	return 0;
}

证明

这里有一份时代久远的关于上面式子的证明：

引理：欧拉函数的积性 构造一个$n\times m$（$\gcd(n,m)=1$）的矩阵：

$$\begin{bmatrix} 1&2&\cdots&m\\ m+1&m+2&\cdots&2m\\ \vdots&\vdots&&\vdots\\ (n-1)m+1&(n-1)m+2&\cdots&nm \end{bmatrix} $$

易知每一行都是m的完全剩余系，那么对于所有$a_{i,j}$，都有$a_{i,j}\bmod m=(i-1)*m+j-(i-1)*m=j$。 因此有$\forall_{1\leqslant i\leqslant n}\left\{a_{i,1},a_{i,2},\cdots,a_{i,m}\right\}\in\left\{km,km+1,km+2,\cdots,(k+1)m-1\right\}(k\in\mathbb{N})$。 也很容易证明每一列都是$n$的完全剩余系。 反证法：设$(i_1,j)$与$(i_2,j)$模$n$同余，且$i_1\not=i_2$，那么$(i_1-1)\times m+j\equiv (i_2-1)\times m+j(mod\ n)$。 也就是$(i_1-1)\times m+j=k_1\times n+r,(i_2-1)\times m+j=k_2\times n+r$。 两式相减得$(i_1-i_2)\times m=(k_1-k_2)\times n$。 又因为$\gcd(n,m)=1$，所以$(i_1-i_2)\mid n$那么不难发现$i_1=i_2$，所以每一列都是$n$的完全剩余系。 由欧拉函数的定义得矩阵内可以找到$\varphi(m)$列，其中有$\varphi(n)$个元素同时与m和n互素，即共$\varphi(m)\times\varphi(n)$个元素与$m$和$n$互素，也就是与$n\times m$互素。

然后证明欧拉函数的公式：对于$n=\prod_{i=1}^s p_i^k$，满足$\varphi(n)=n\times\prod_{i=1}^s\frac{p_i-1}{p_i}$。

首先很显然$n$为质数的时候，$\varphi(n)=n\times\frac{n-1}{n}$。

然后是$n=p^k$时（$p$为质数，$k\in\mathbb{N^{+}}$）：

很容易证明$\forall 1\leqslant m\leqslant n$，$p\not\mid m$与$\gcd(m,n)=1$等价，那么可以发现与$n$不互素的数只有$p,2p,\cdots p^k$这$p^{k-1}$个数。

那么$\varphi(n)=n-p^{k-1}=p^k\times\frac{p-1}{p}=n\times\frac{p-1}{p}$。

当$n$为任意正整数时，设$n=\prod_{i=1}^s p_i^{k_i}$，由$\varphi$的积性可知$n=\prod_{i=1}^s \varphi(p_i^{k_i})=\prod_{i=1}^s(p^{k_i}\times\frac{p-1}{p})=n\times\prod_{i=1}^s\frac{p_{i-1}}{p_i}$。