这道题很巧妙，要把式子变一下
phi(n) = n * (1 - 1 / p1) * (1 - 1 / p2)……(1 - 1 / pr)
= n * ((p1-1) / p1) * ((p1-2) / p2) ……((pr-2) / pr)
= p1^k1 * p2^k2……pr^kr * ((p1-1) / p1) * ((p1-2) / p2) ……((pr-2) / pr)
= p1^(k1-1) * (p1-1) * p2^(k2-1) * (p2-1)……pr^(kr-1) * (pr-1)
因为幂可以为0，所以不能直接质因数分解，要枚举枚举p1-1
计算的过程中phi(n)第一次除以(pr-1),答案就乘以pr，后来 phi(n)每次都是除以pr
答案乘以pr。因为n = p1^k1 * p2^k2……pr^kr，而phi(n) = p1^(k1-1) * (p1-1) * p2^(k2-1) * (p2-1)……pr^(kr-1) * (pr-1)
很多博客没有把这里讲清楚。
另外素数表打到根号10的八次方，也就是一万就可以了，最后一个单独暴力判断，还要注意之前没有用过。
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int MAXN = 11234;
bool is_prime[MAXN], vis[MAXN];
vector<int> prime, g;
int ans;void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, MAXN){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()){if(i * prime[j] > MAXN) break;is_prime[i * prime[j]] = false;if(i % prime[j] == 0) break;}}
}void init(int n)
{ans = 2e9;g.clear();REP(i, 0, prime.size())if(n % (prime[i] - 1) == 0)g.push_back(prime[i]);
}bool judge(int sum)
{REP(i, 0, prime.size()){if(prime[i] * prime[i] > sum) break;if(sum % prime[i] == 0) return false;}REP(i, 0, prime.size())if(vis[i] && prime[i] == sum)return false;return true;
}void dfs(int p, int sum, int tot)
{if(p == prime.size()){if(sum == 1) ans = min(ans, tot);else if(judge(sum + 1))ans = min(ans, tot * (sum + 1));return;}dfs(p + 1, sum, tot);if(sum % (prime[p] - 1)) return;vis[p] = 1;sum /= prime[p] - 1;tot *= prime[p];dfs(p + 1, sum, tot);while(sum % prime[p] == 0){sum /= prime[p];tot *= prime[p];dfs(p + 1, sum, tot);}vis[p] = 0;
}int main()
{get_prime();int n, kase = 0;while(~scanf("%d", &n) && n){init(n);memset(vis, 0, sizeof(vis));dfs(0, n, 1);printf("Case %d: %d %d\n", ++kase, n, ans);}return 0;
}