首页 > 代码库 > 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;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。