求欧拉函数$\varphi$

$O(\sqrt)$时间复杂度的算法

首先我们要求$\varphi$(x)，可以先将其分解成$\prod(a_i^{p_i})$的形式，其中$a$是素数。
然后可以推导出公式$\varphi$(x)=$\prod(a_i^{p_i}-a_i^{p_i-1})$
然后这个可以实现为$\varphi$(x)=$x/\prod(a_i-1)$
这样就可以在$\sqrt{}$时间内出解了。

线性时间复杂度的算法

线性筛！
因为欧拉函数是积性函数，所以我们可以采用线性筛。
过程见下方代码getphi()函数。

基于欧拉函数的求逆元

首先有欧拉公式 $x^{\varphi(p)}$%$p==1$
所以$x*x^{\varphi(p)-1}$%$p==1$
这样$x^{\varphi(p)-1}$就是x在$mod$ $p$ 意义下的逆元。

$O(log)$时间复杂度求逆元

不考虑求$\varphi$，我们通过快速幂求逆元的时间复杂度是$O(log)$级别的

线性时间复杂度的算法

同样是线性筛，代码在下面。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
using namespace std;
int Phi(int x)
{
    int i,ans=x;
    for(i=2;i*i<=x;i++)if(x%i==0)
    {
        ans/=i,ans*=i-1;
        while(x%i==0)x/=i;
    }
    if(x>1)ans/=x,ans*=x-1;
    return ans;
}
int prime[N],phi[N],num;
bool vis[N];
void getphi(int n=1000000)
{
    int i,j,k;
    phi[1]=1;
    for(i=2;i<=n;i++)
    {
        if(!vis[i])prime[++num]=i,phi[i]=i-1;
        for(j=1;j<=num;j++)
        {
            k=i*prime[j];
            if(k>n)break;
            vis[k]=1;
            if(i%prime[j]==0)
            {
                phi[k]=phi[i]*prime[j];
                break;
            }
            phi[k]=phi[i]*(prime[j]-1);
        }
    }
    return ;
}
long long inv[N],p;
long long power(long long x,int k)
{
    long long ans=1;
    while(k)
    {
        if(k&1)ans=ans*x%p;
        x=x*x%p,k>>=1;
    }
    return ans;
}
long long Inv(long long x){return power(x,phi[p]-1);}
void getinv(int n=1000000)
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(long long)(p-p/i)*inv[p%i]%p;
}
int main()
{
    scanf("%d",&p);
    getphi();
    getinv();
}