题解 P4930【[PA2013]Euler】
whiteqwq
·
·
题解
P4930 [PA2013]Euler解题报告：
更好的阅读体验
题意
## 分析
原来的题目数据有锅，修完数据后拿到了首杀。
搜索题。
首先$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}$。