已知欧拉函数计算公式
初始公式：φ(n)=n*(1-1/p1)*(1-1/p2).....*(1-1/pm)
又 n=p1^a1*p2^a2*...*ps^as 欧拉函数是积性函数
那么：φ（n）=φ（p1^a1）* φ(p2^a2)........φ(pn^an).
#include<cstdio> #include<ctime> #include<iostream> #include<cstdlib> #include<algorithm> #define LL long long #define maxn 100010 #define MAXN 10000000 using namespace std; LL n,k,prime[MAXN/10],cnt,ans[maxn]; bool mark[MAXN+10]; void first() { for(int i=2;i<=MAXN;i++) { if(!mark[i]) prime[++cnt]=i; for(int j=1;j<=cnt;j++) { if(i*prime[j]>MAXN) break; mark[i*prime[j]]=1; if(i%prime[j] ==0) break; } } return ; } LL mul(LL a,LL b,LL mod) { LL ans=0; while(b) { if(b&1) ans=(ans+a)%mod; a=(a<<1)%mod;b>>=1; } return ans; } LL low(LL a,LL b,LL mod) { LL ans=1; while(b) { if(b&1) ans=mul(ans,a,mod); b>>=1,a=mul(a,a,mod); } return ans; } bool Is_prime(LL n) { if(n<2) return 0; if(n==2) return 1; if(n%2 ==0) return 0; LL m=n-1,j=0; while(m%2 == 0) { j++; m>>=1; } for(int i=1;i<=5;i++) { LL a=rand()%(n-1)+1; LL x=low(a,m,n); LL y; for(int k=1;k<=j;k++) { y=mul(x,x,n); if(y==1&&x!=1&&x!=n-1 ) return 0; x=y; } if(x!=1) return 0; } return 1; } void dfs(LL x,LL y,LL mod ) { if(x==1) { ans[++ans[0]]=y; return ; } if(x+1 > prime[cnt] && Is_prime(x+1)) ans[++ans[0]]=y*(x+1); for(int i=mod;i>=1;i--) if(x%(prime[i]-1) == 0) { LL a=x/(prime[i]-1),b=y,c=1; while(a%c ==0) { b*=prime[i]; dfs(a/c,b,i-1); c*=prime[i]; } } } int main() { freopen("arc.in","r",stdin); freopen("arc.out","w",stdout); scanf("%lld%lld",&n,&k); srand(time(0)); first(); dfs(n,1,cnt); sort(ans+1,ans+1+ans[0]); for(int i=1;i<=k;i++) printf("%lld ",ans[i]); return 0; }