UVA 10837 A Research Problem

https://vjudge.net/problem/UVA-10837

求最小的n，使phi（n）=m

#include<cstdio>

#include<algorithm>

#define N 10011

int prime[N],cnt;

bool v[N],vis[N];

int p[N],tot,ans;

void pre_prime()

{

    for(int i=;i<N;i++)

    {

        if(!v[i]) prime[++cnt]=i;

        for(int j=;j<=cnt;j++)

        {

            if(i*prime[j]>=N) break;

            v[i*prime[j]]=;

            if(i%prime[j]==) break;

        }

    }

}

int judge(int n)

{

    if(n==) return ;

    n++;

    for(int i=;i<=cnt && prime[i]*prime[i]<=n;i++)

        if(n%prime[i]==) return -;

    for(int i=;i<=tot;i++)

        if(vis[i] && n==p[i]) return -;

    return n;

}

void dfs(int now,int left,int sum)

{

    if(sum==tot+)

    {

        int ret=judge(left);

        if(ret>) ans=std::min(ans,now*ret);

        return;

    }

    dfs(now,left,sum+);

    if(left%(p[sum]-)==)

    {

        vis[sum]=;

        now*=p[sum];

        left/=p[sum]-;

        while()

        {

            dfs(now,left,sum+);

            if(left%p[sum]) break;

            left/=p[sum];now*=p[sum];

        }

        vis[sum]=;

    }

}

void solve(int n)

{

    tot=; ans=2e9;

    for(int i=;i<=cnt && n>=(prime[i]-)*(prime[i]-);i++)

        if(n%(prime[i]-)==)

        p[++tot]=prime[i];

    dfs(,n,);

}

int main()

{

    pre_prime();

    int n,t=;

    while(scanf("%d",&n)!=EOF)

    {

        if(!n) return ;

        solve(n);

        printf("Case %d: %d %d\n",++t,n,ans);

    }

}