数学+暴搜 Phi的反函数

               ----------

欧拉定理： phi(n)=(p1^x1)(p2^x2)… (1-1/p1) *(1/1/p2)….
也就是说，phi(n)=p1^(x1-1)(p1-1) ……
而现在，我们知道了phi(x)=n,要求 x，而x=p1^x1*p2^x2 *…

               ----------

根据常识（我现学的。。），最多分解出10个左右质因数。那就可以暴搜了。
把素数的表打出来，找出满足的（pri[i]-1），之后枚举pri[i]的次方。累计求出sum,与ans比较即可。
最后设剩余x,只要判断x+1是质数即可（具体不再解释）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 2147483647
using namespace std;
int n,m,pri[50000],mark[50000],tot;
ll ans=2147483658ll;
inline bool check(int x)
{
    int hh=(int)sqrt(x);
    for(int i=1;pri[i]<=hh;i++)if(x%pri[i]==0)return 0;
    return 1;
}
inline void dfs(int i,int x,ll y)
{
    if(y>=ans)return;
    if(x==1){ans=y;return;}
    if(x>m&&check(x+1)){ans=min(ans,y*(x+1));}
    for(i=i+1;pri[i]-1<=m;i++)
    {
        if(pri[i]>x)break;
        if(x%(pri[i]-1)==0)
        {
            int l=x/(pri[i]-1);ll h=y*pri[i];
            dfs(i,l,h);
            while(l%pri[i]==0)
            {
                l/=pri[i];h*=pri[i];
                dfs(i,l,h);
            }
        }
    }
}
int main()
{
    scanf("%d",&n);m=sqrt(n);
    for(int i=2;i<=m+5;i++)
    {
        if(!mark[i])pri[++tot]=i;
        for(int j=1;j<=tot;j++)
        {
            if(pri[j]*i>m)break;
            mark[pri[j]*i]=1;
            if(i%pri[j]==0)break;
        }
    }
    dfs(1,n,1);
    if(ans<=N)printf("%lld",ans);
    else cout<<-1;
}