平时看到的题目是给n求phi(n) 现在是给phi(n)求一个最小n
当一个数为素数是m=n*(1-1/n);
例如 12=13(1-1/13);所以可以得出 m%(n-1)==0 时，n-1为n的素因子
m=n*(1-1/p1)*(1-1/pn);
n=p1^x1*(p1-1)*p2^x2(p2-1)......;
#include <iostream> #include <stdio.h> #include <cmath> #include <algorithm> #include <iomanip> #include <cstdlib> #include <string> #include <memory.h> #include <vector> #include <queue> #include <stack> #include <map> #include <set> #define ll long long #define INF 1000000 #include<time.h> using namespace std; #define ll long long #define maxn 10005 #define ULL unsigned long long #define MST(vis,x) memset(vis,x,sizeof(vis)) #define tempmaxn 200000000 int vis[maxn]; int prim[maxn]; int all; void init() { all=1; for(int a=2; a<=10000; a++) { if(vis[a]==0) prim[all++]=a; for(int b=1; b<all&&prim[b]*a<=10000; b++) { vis[prim[b]*a]=1; if(a%prim[b]==0)break; } } return; } int ans; int s1[maxn],vs[maxn]; int op; void getprim(int n) { for(int a=1; (a<all)&&(prim[a]-1)*(prim[a]-1)<=n; a++) if(n%(prim[a]-1)==0) s1[op++]=prim[a]; return; } bool judge(int n) { if(n==2)return true; for(int a=1;a<all&&prim[a]*prim[a]<=n;a++) if(n%prim[a]==0) return false; for(int a=1;a<op;a++) if(vs[a]&&s1[a]==n) return false; return true; } void cir(int tempsum,int tempn,int tempop) { if(tempop==op) { if(judge(tempn+1)) { if(tempn==1) tempn=0; ans=min(ans,tempsum*(tempn+1)); } return; } cir(tempsum,tempn,tempop+1); if(tempn%(s1[tempop]-1)==0) { vs[tempop]=1; tempn/=(s1[tempop]-1); tempsum*=s1[tempop]; while(true) { cir(tempsum,tempn,tempop+1); if(tempn%s1[tempop]==0) { tempn/=s1[tempop]; tempsum*=s1[tempop]; } else return ; } vs[op]=0; } return; } int solve(int n) { ans=0x3f3f3f3f; op=1; MST(vs,0); MST(s1,0); getprim(n); cir(1,n,1); if(ans==INF)ans=0; return ans; } int main() { init(); int n,i=1; while(scanf("%d",&n)!=EOF) { if(!n)break; printf("Case %d: %d %d\n",i++,n,solve(n)); } return 0; }