P4930 [PA2013]Euler解题报告

解题报告

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$中为质数的值存入$D_{1\cdots Ds}$，不难发现$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}$。