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;

}