Luogu | P4780 Phi 的反函数 | 数学 | 欧拉函数

---

Description

请求出最小的正整数 $x$ ，使得 $\phi_x = N$。

---

Input Format

一行一个正整数 $N$ 。

---

Output Format

输出 $x$ ，若 $x$ 不存在或者 $x > 2^{31}$，输出 $-1$。

---

Input Sample

Sample 01

4

---

Output Sample

Sample 01

5

---

Data Range

$1 \le N \le 2^{31}$。

---

Solution

显然 $\phi$ 在其定义域上无单调性，故只能用 DFS 枚举。

根据 $\phi$ 的定义，考虑筛出 $\sqrt{2^{31}}$ 以内的所有质数，然后进行 DFS 。观察数据范围，可以发现，范围内的数字最多由 $10$ 个不同质数组成，每个质数最多有 $30$ 个。所以数据范围较小。

根据 $\phi$ 的部分积性和递推求法，可以发现，设当前还剩的 $\phi$ 为 $p$ ，当前已经形成的数字为 $x$ 。当 $p$ 内存在因子 $e$并且 $e+1$ 是一个质数，则可以将该 $e+1$ 乘进 $x$ 内，再从 $p$ 中分离质因子 $e$ 。可能出现剩下 $p+1$ 是一个大于 $\sqrt N$ 的大质数的情况，那么将对应的 $p+1$ 乘进 $x$ 即可。

---

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

int N;
int cnt;

long long ans=4294967296;

int primes[50005];

bool isprime[50005];

void Euler_Sieve(int lim){
    rep(i,2,lim){
        if(!isprime[i])
            primes[++cnt]=i;
        for(int j=1;j<=cnt&&i*primes[j]<=lim;j++){
            isprime[i*primes[j]]=1;
            if(i%primes[j]==0)
                break;
        }
    }
    return;
}

bool isPrime(int a){
    if(a<0)
        return false;
    for(int i=1;primes[i]*primes[i]<=a;i++){
        if(a%primes[i]==0)
            return false;
    }
    return true;
}

void DFS(int step,long long Phi,long long num){
    if(Phi==1){
        ans=min(ans,num);
        return;
    }
    if((Phi*Phi>N)&&isPrime(Phi+1)){
        if((Phi+1)*num<ans)
            ans=min(ans,(Phi+1)*num);
        return;
    }
    rep(i,step,cnt){
        if(Phi%(primes[i]-1)==0){
            long long Next=Phi;
            long long Num=num;
            while(Next%(primes[i]-1)==0){
                Next/=(primes[i]-1);
                Num*=primes[i];
                if(Num<0||Num>ans) break;
                DFS(i+1,Next,Num);
            }
        }
    }
    return;
}

int main(){
    Read(N);
    Euler_Sieve(46340);
    if(isPrime(N+1)){
        printf("%d\n",N+1);
        return 0;
    }
    DFS(1,N,1);
    printf("%lld\n",ans==4294967296?-1:ans);
    return 0;
}