题解 P4780 【Phi的反函数】

· · 题解

最多有10个质数，因为2*3*5*7*11*13*17*19*23*29=6469693230 一个质数最多有30个，因为2^{31}=2147483648 均大于等于2^{31}，故应为-1。

可见，本题数据范围较小，可用dfs来完成。

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define LL long long
int tot,vis[46500];
LL prime[4800];
void init(){  //预处理素数
    prime[++tot]=2;
    for(int i=3;i<=46400;i+=2)
    if(!vis[i]){
        prime[++tot]=i;int qq=i<<1;
        for(int j=i*3;j<=46400;j+=qq)
        if(!vis[j])vis[j]=1;
    }
    //4796 primes
}
LL n,ans=4294967296;
bool pr(LL qq){  //判断单个数字是否为素数
    if(qq&1^1)return false;
    int rr=sqrt(qq);
    for(int i=3;i<=rr;i+=2)
    if(qq%i==0)return false;
    return true;
}
void dfs(int pri,LL num,LL phi){
    if(num==1){  //若该数已经被拆完，直接更新答案
        ans=min(ans,phi);
        return;
    }
    if(num>sqrt(n)&&pr(num+1)){  //若当前数大于sqrt(n)，那么可能为质数且只有一个，故进行判断
        ans=min(ans,phi*(num+1)); //若是质数直接更新答案
        return;
    }
    for(int i=pri+1;i<=tot&&(prime[i]-1)<=num;i++) //枚举所有质数
    if(num%(prime[i]-1)==0){
        LL num_=num/(prime[i]-1);
        LL phi_=phi*prime[i];  //计算新的数字和答案
        dfs(i,num_,phi_);  //下一轮dfs
        while(num_%prime[i]==0){//枚举该质数的次数
            num_/=prime[i];   //计算新的数字和答案
            phi_*=prime[i];
            dfs(i,num_,phi_);  //下一轮dfs
        }
    }
}
int main(){
    init();   //得到sqrt(2147483647)以内的质数 
    scanf("%d",&n);
    dfs(0,n,1);  //进行dfs，一定要初始化答案为1
    if(ans!=4294967296)printf("%lld\n",ans);
    else puts("-1");  //输出答案
}