输入正整数m(m≤1e8),求最小的正整数n,使得φ(n)=m。n<=2e8。
#include<cstring> #include<algorithm> #include<iostream> #include <map> using namespace std; const int M=1e5+5; #define int long long #define inf 1e9 int tot,prime[M],vis[M]; int vec[M],vsize; int ans =inf; void init(int top){ int i,j; vis[1]=1; for(i=2;i<=top;i++){ if(vis[i]) continue; prime[++tot]=i; for(j=i*2;j<=top;j+=i) vis[j]=1; } } void shai(int x){ vsize=0; for(int i=1;i<=tot&&(prime[i]-1)*(prime[i]-1)<=x;i++){ if(x%(prime[i]-1)==0) vec[++vsize]=prime[i]; } } bool chk(int x){ for(int i=1;i<=tot&&prime[i]*prime[i]<=x;i++){ if(x%prime[i]==0) return 0; } for(int i=1;i<=vsize;i++){ if(vis[i] && x==vec[i]) return 0 ; } return 1; } void dfs(int cnt,int num,int A){ if(cnt>vsize){ if(num==1) ans=min(ans,A); else if(chk(num+1)){ A*=(num+1); ans=min(ans,A); } return ; } dfs(cnt+1,num,A); if(num%(vec[cnt]-1)) return ; vis[cnt]=1; dfs(cnt+1,num/=(vec[cnt]-1),A*=vec[cnt]) ; while(num%vec[cnt]==0){ num/=vec[cnt],A*=vec[cnt] ; dfs(cnt+1,num,A) ; } vis[cnt]=0; } signed main() { init(1e5); int m,cas=0; while(cin>>m,m){ shai(m); memset(vis,0,sizeof vis); ans=inf; // cout<<"len: "<<vsize<<"\n\n"; dfs(1,m,1); printf("Case %lld: %lld %lld\n",++cas,m,ans); } }