3643: Phi的反函数

Time Limit: 10 Sec  Memory Limit: 64 MB

Description

Input

 

Output

 

Sample Input

4

Sample Output

5

HINT

 

Source

 

Tips：

　　自己也没怎么搞懂；

 

Code：

#include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 200008using namespace std;long long n,m,prime[MAXN],tot,flag[MAXN],ans;void init(){    for(long long i=2;i<=MAXN-8;i++){        if(!flag[i]){            flag[i]=1;            prime[++tot]=i;        }        for(long long j=1;j<=tot&&i*prime[j]<=MAXN-8;j++){            flag[i*prime[j]]=1;            if(i%prime[j]==0) break;        }    }}bool check(long long u){    for(int i=1;prime[i]*prime[i]<=u;i++){        if(u%prime[i]==0) return 0;    }    return 1;}void dfs(long long x,long long y,long long z){    if(z>=ans) return;    if(y==1){        ans=min(ans,z);        return;    }    if(y*y>n&&check(y+1)){        ans=min(ans,z*(y+1));        return;    }    for(int i=x;prime[i]-1<=y&&(prime[i]-1)*(prime[i]-1)<=n;i++)    if(y%(prime[i]-1)==0){        long long xx=y    /(prime[i]-1);        long long yy=z*prime[i];        dfs(i+1,xx,yy);        while(xx%prime[i]==0){            xx=xx/prime[i];            yy=yy*prime[i];            dfs(i+1,xx,yy);        }    }}int main(){    tot=0;    ans=(long long)1<<31;    init();    scanf("%lld",&n);    dfs(1,n,1);    if(ans==(long long)1<<31){        printf("-1");    }else{        printf("%lld",ans);    }}