P4780 Phi的反函数题解

Steadywelkin · 2021-04-10 13:05:53 · 题解

P4780 Phi的反函数

在做本题之前先回顾一些欧拉函数的性质：

如果有 \gcd(a,b)=1，那么 \varphi(a\times{b})=\varphi(a)\times\varphi(b)
n=\sum_{d|n}\varphi(d)
由唯一分解定理， \varphi(n)=n\times\prod_{i=1}^s\frac{p_i-1}{p_i}
对于一个素数，有 \varphi(n)=n-1

下面是对于单一的数值的欧拉函数求解：

inline int getphi(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            for(;n%i==0;n/=i);
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

可以发现，对于每一个素数，不管它在这个数被分解后出现了几次，它对整个数的欧拉函数的取值的贡献都只会被计入一次（这在欧拉函数的第三条性质中可以看出来）。

那么反过来，对于一个欧拉函数值要求出最小的数时，对于每一个分解后的素数我们都只出现一次必然是最优的。

考虑对数进行分解，可以采取试除法，注意我们分解的是欧拉函数值，真实的素数值应当是分解的数加上一，判断时可以采用米勒拉宾算法。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ull;

inline ull read()
{
    ull a=0,f=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar())
        if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())
        a=(a<<3)+(a<<1)+ch-'0';
    return a*f;
}

const ull INF=1e18;
const int N=1e6;
ull ans=INF,n,st[N]={-1},top;

inline ull qmul(ull a,ull b,ull p)
{
    a%=p;b%=p;
    return (a*b-(ull)((long double)a/p*b)*p+p)%p;
}

inline ull qpow(ull a,ull n,ull p)
{
    ull ans=1;
    for(;n;n>>=1)
    {
        if(n&1) ans=ans*a%p;
        a=a*a%p;
    }
    return ans;
}

inline bool miller_rabin(ull n)
{
    if(n==2) return true;
    if(n<2||!(n&1)) return false;
    ull m=n-1,k=0;
    for(;!(m&1);k++,m>>=1);
    for(int i=1;i<=20;i++)
    {
        ull a=rand()%(n-1)+1;
        ull x=qpow(a,m,n),y;
        for(int j=1;j<=k;j++)
        {
            y=qmul(x,x,n);
            if(y==1&&x!=1&&x!=n-1)
                return false;
            x=y;
        }
        if(y!=1) return false;
    }
    return true;
}

void dfs(int now,ull x,ull tmp)
{
    if(tmp>=ans) return;
    if(x==1){ans=tmp;return;}
    if(miller_rabin(x+1))
        dfs(now+1,1,tmp*(x+1));
    for(int i=2;i*i<=x;i++)
        if(x%i==0&&i>st[now-1]&&miller_rabin(i+1))
            st[now]=i,dfs(now+1,x/i,tmp*(i+1));
    return;
}

signed main()
{
    n=read();
    dfs(1,n,1);
    if(ans>2147483648ull)puts("-1");
    else printf("%llu\n",ans);
    return 0;
}

P4780 Phi的反函数 题解

P4780 Phi的反函数题解