题解P4780

reclusive · 2022-10-12 11:21:20 · 题解

题目大意：

传送门：P4780 Phi的反函数

这道题就是让你去求一个最小的正整数 x，使得 \varphi(x)=n。

具体思路：

在那之前，我们先来讲一些欧拉函数的性质。

性质：

若 n\in prime, 则有：\varphi(n)=n-1。
欧拉函数为积性函数，有：\varphi(ab)=\varphi(a)\varphi(b)。
由唯一分解定理，设 n=\prod_{i=1}^sp_i^{k_i}，其中，p_i\in prime，有：\varphi(n)=n\times\prod_{i=1}^s\dfrac{p_i-1}{p_i}。

证明：略，以上性质证明可以去 bdfs 一下。（~~真的不是我不会啊~~）

思路：

首先，我们对 x 分解质因数，设 x=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}，即 x=\prod_{i=1}^s p_i^{c_i}。

由于 \varphi(x) 是积性函数，因此 \varphi(x)=\varphi(p_1^{c_1})\varphi(p_2^{c_2})\dots \varphi(p_k^{c_k})，即 \varphi(x)=\prod_{i=1}^s\varphi(p_i^{c_i})。

但是题目求的是 x 的最小正整数解，那怎样的 x 才能保证是最小正整数解呢？

我们仔细观察式子：

\varphi(n)=n\times\prod_{i=1}^s\dfrac{p_i-1}{p_i}

上式中 \varphi(n) 的值与 p_i 的指数 c_i 无关，也就是一个数的欧拉函数值与质因子的指数无关。

那就很好求最小正整数解了，我们只要令 x 的所有质因子指数都为 1,即 x=\prod_{i=1}^s p_i。

因此，原式化为 n=\prod_{i=1}^s \varphi(p_i)，其中 p_i\in prime。

那我们又知道若 n\in prime，则有 \varphi(n)=n-1，

所以，原式又可以化简为：n=\prod_{i=1}^s (p_i-1)。

那接下来的思路都很容易想到了，我们用线性筛先将一部分的质数找出来，然后直接 dfs 来将 n 分解为几个质数 -1 的乘积。

不过，这道题需要一个剪枝，就是如果你当前要分解的 n 是一个很大的质数，你线性筛的时候没把它找出来，然后分解的时候一直跑，可能会导致 TLE，

所以我们可以在分解 n 之前，就可以判断 n 是不是一个质数，如果是，直接 dfs，可以省下一点时间。

然后你判断质数时，可以采用最传统的试除法，当然也可以像我一样用新学的 Miller-Robin 算法，可能可以快一点，不过我也试了一下两种方法，都是可以过的。

最后给一点小 Tips:

没事不要全部变量都开 long long。
用 Miller-Robin 时，常数记得开小一点，开 20 已经可以得出正确答案了，开 50 直接 TLE 了，更别说 114514 了！

AC Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5;
LL v[N+10],prime[N+10],pr,ans=0x7fffffff;
inline int read()//快读 
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'&&ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void write(int s)//快输 
{
    int n=0,buf[15];
    if(s<0) putchar('-'),s=-s;
    do buf[n++]=s%10;while(s/=10);
    while(n--) putchar(buf[n]+'0');
}
LL witness(LL a,int n)
{
    LL ans=1,t=n-1,x;
    while(t)
    {
        if(t&1)ans=ans*a%n;
        x=a;a=a*a%n;
        if(a==1&&x!=1&&x!=(n-1))return 1;
        t>>=1;
    }
    return (ans==1)?0:1;
}
int Miller_Robin(LL n,int s)
{
    if(n==2)return 1;
    if(n<2||!(n&1))return 0;
    LL a;
    for(int i=0;i<s;++i)
    {
        a=rand()*(n-2)/RAND_MAX+1;
        if(witness(a,n))return 0;
    }
    return 1;
}//以上部分为Miller Robin算法,可以bdfs学习一下 
void init()//线性筛,别筛太大的质数,可能会TLE 
{
    memset(v,0,sizeof(v));pr=0;
    for(int i=2;i<=N;++i)
    {
        if(!v[i])prime[++pr]=i;
        for(int j=1;j<=pr&&i*prime[j]<=N;++j)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}
void dfs(int k,LL n,LL x)
{
    if(n==1){ans=min(ans,x);return;}
    if(Miller_Robin(n+1,20)){dfs(114514,1,x*(n+1));return;}//剪枝 
    for(int i=k;i<=pr;++i)//分解n 
    {
        if(n%(prime[i]-1)==0)
        {
            dfs(i+1,n/(prime[i]-1),x*prime[i]);
            LL nn=n/(prime[i]-1),xx=x*prime[i];
            while(nn%prime[i]==0){nn=nn/prime[i];xx=xx*prime[i];dfs(i,nn,xx);}
        }
    }
}
int main()
{
    init();//预处理 
    int n;n=read();//输入 
    dfs(1,n,1);
    write((ans==0x7fffffff)?-1:ans);//如果ans的值没有被修改到,直接输出-1,否则输出ans 
    return 0;//完结撒花
}