发现自己搜索真的很弱，也许做题太少了吧。代码大部分是参考别人的，=_=||
题意：
给出一个phi(n)，求最小的n
分析：
回顾一下欧拉函数的公式：，注意这里的Pi是互不相同的素数，所以后面搜索的时候要进行标记。
先找出所有的素数p，满足(p - 1)整除题目中所给的phi(n)
然后暴搜。。
素数打表打到1e4就够了，如果最后剩下一个大素数单独进行判断。
1 #include <cstdio> 2 #include <cmath> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 10000; 8 const int INF = 200000000; 9 10 int phi_n, ans; 11 12 bool vis[maxn + 10]; 13 int prime[1500], pcnt = 0; 14 int fac[1500], tot; 15 16 void prime_table() 17 { 18 int m = sqrt(maxn + 0.5); 19 for(int i = 2; i <= m; i++) if(!vis[i]) 20 for(int j = i * i; j <= maxn; j += i) vis[j] = true; 21 for(int i = 2; i <= maxn; i++) if(!vis[i]) prime[pcnt++] = i; 22 } 23 24 void factor(int n) 25 { 26 tot = 0; 27 for(int i = 0; i < pcnt && (prime[i]-1) * (prime[i]-1) <= n; i++) if(n % (prime[i] - 1) == 0) 28 fac[tot++] = prime[i]; 29 } 30 31 int judge(int n) 32 { 33 if(n == 1) return 1; 34 n++; 35 //判断剩余的phin中加1后是否为素数 36 for(int i = 0; i < pcnt && prime[i] * prime[i] <= n; i++) if(n % prime[i] == 0) 37 return -1; 38 //如果为素数的话，判断是否标记过 39 for(int i = 0; i < tot; i++) if(vis[i] && n == fac[i]) 40 return -1; 41 return n; 42 } 43 44 void dfs(int n, int phin, int d) 45 { 46 if(d == tot) 47 { 48 int t = judge(phin); 49 if(t > 0) ans = min(ans, n * t); 50 return; 51 } 52 53 dfs(n, phin, d+1); 54 if(phin % (fac[d] - 1) == 0) 55 { 56 vis[d] = true; 57 n *= fac[d]; 58 phin /= (fac[d] - 1); 59 for(;;) 60 { 61 dfs(n, phin, d+1); 62 if(phin % fac[d] != 0) 63 return; 64 phin /= fac[d]; n *= fac[d]; 65 } 66 } 67 vis[d] = false; 68 } 69 70 int main() 71 { 72 freopen("in.txt", "r", stdin); 73 74 int kase = 0; 75 prime_table(); 76 while(scanf("%d", &phi_n) == 1 && phi_n) 77 { 78 ans = INF; 79 memset(vis, false, sizeof(vis)); 80 factor(phi_n); 81 dfs(1, phi_n, 0); 82 printf("Case %d: %d %d ", ++kase, phi_n, ans); 83 } 84 85 return 0; 86 }