uva 10837 - A Research Problem(欧拉函数+暴力)

本文主要是介绍uva 10837 - A Research Problem(欧拉函数+暴力)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 10837 - A Research Problem

题目大意：给定一个phin，要求一个最小的n，欧拉函数n等于phin

解题思路：欧拉函数性质有，p为素数的话有phip=p−1;如果p和q互质的话有phip∗q=phip∗phiq
然后根据这样的性质，n=pk11(p1−1)∗pk22(p2−1)∗⋯∗pkii(pi−1),将所有的pi处理出来，暴力搜索维护最小值，虽然看上去复杂度非常高，但是因为对于垒乘来说，增长非常快，所以搜索范围大大被缩小了。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
const int maxp = 1e4;
const int INF = 0x3f3f3f3f;int ans;
int np, vis[maxp+5], pri[maxp+5];
int nf, fact[maxp+5], v[maxp+5];void prime_table (int n) {np = 0;for (int i = 2; i <= n; i++) {if (vis[i])continue;pri[np++] = i;for (int j = i * i; j <= n; j += i)vis[j] = 1;}
}void get_fact (int n) {nf = 0;for (int i = 0; i < np && (pri[i]-1) * (pri[i]-1) <= n; i++) {if (n % (pri[i]-1) == 0)fact[nf++] = pri[i];}
}bool judge (int n) {if (n == 2)return true;for (int i = 0; i < np && pri[i] * pri[i] <= n; i++)if (n % pri[i] == 0)return false;for (int i = 0; i < nf; i++)if (v[i] && fact[i] == n)return false;return true;
}void dfs (int ret, int cur, int d) {if (d == nf) {if (judge(cur+1)) {if (cur == 1)cur = 0;ans = min(ans, ret * (cur+1));}return;}dfs(ret, cur, d+1);if (cur % (fact[d]-1) == 0) {v[d] = 1;ret *= fact[d];cur /= (fact[d]-1);while (true) {dfs(ret, cur, d+1);if (cur % fact[d])return;ret *= fact[d];cur /= fact[d];}v[d] = 0;}
}int solve (int n) {ans = INF;get_fact(n);memset(v, 0, sizeof(v));dfs(1, n, 0);return ans;
}int main () {prime_table(maxp);int cas = 1, n;while (scanf("%d", &n) == 1 && n) {printf("Case %d: %d %d\n", cas++, n, solve(n));}return 0;
}