BZOJ-3643: Phi的反函数

Description

定义给定n< 2^31，求，若答案不存在或大于2^31则输出-1

和上一个约数和等于定值的解法一样。
x分解质因数

枚举小于根号的质因子搜索，如果剩下的因子+1等于一个大于枚举上界的质数或剩下的因子为1则找到一个解。

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 201000
typedef long long ll;
int n,sq,pri[N],cnt;
ll ans=1ll<<62;
bool v[N];
void initialize()
{
    int i,j;
    for(i=2;i<=200000;++i)
    {
        if(!v[i]) pri[++cnt]=i;
        for(j=1;i*pri[j]<=200000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}
bool ispri(int x)
{
    if(x<=200000) return !v[x];
    for(int i=1;pri[i]*pri[i]<=x;++i) if(x%pri[i]==0) return false;
    return true;
}
void dfs(int now,ll tmp,int leave)
{
    if(tmp>1ll<<31||tmp>=ans) return ;
    if(leave==1){ans=min(ans,tmp); return ;}
    if(leave+1>=sq&&ispri(leave+1)) ans=min(ans,tmp*(leave+1));
    int i; ll x;
    for(i=now;pri[i]<=sq;++i)
    {
        x=pri[i]-1;
        while(leave%x==0&&tmp*x<1ll<<31)
            dfs(i+1,tmp*x/(pri[i]-1)*pri[i],leave/x),x*=pri[i];
    }
}
int main()
{
    scanf("%d",&n);
    sq=(int)sqrt(n)+1;
    initialize();
    dfs(1,1,n);
    if(ans>(1ll<<31)) puts("-1");
    else printf("%lld",ans);
    return 0;
}