欧拉函数以及欧拉降幂

大数幂运算指数太大的时候，我们需要进行降幂操作。

首先呢，认识欧拉定理之前 先了解一下欧拉函数

欧拉函数性质

1. 若p是一个质数，那么Φ(p)=p-1
2. 欧拉函数是积性函数，所以Φ(nm)=Φ(n)Φ(m)
3. 若n=p^k且p为质数，那么Φ(n)=p^k-p^(k-1)。（证明：因为p为质数，那么p^k能被p整除的就有p^(k-1）个，如此说来，不能被p整除的就是两者相减咯）
4. 当n为奇数时，有Φ(2*n)=Φ(n)
5. ∑(d|n)Φ(d)=n  非常重要的性质！！

欧拉定理

我们将欧拉函数写作

欧拉定理就是a、n为正整数且a、n互质，那么  (mod  n)

那么根据欧拉定理的式子，我们可以转化为  %n=1  

那么既然 在mod n的情况下  恒等于 1  

那么就得到了我们用来降幂的公式(mod n)

扩展欧拉定理

扩展呢就是把互质推广到所有情况嘛
如果欧拉定理中的a、n不互质了  则有如下公式

降幂

如果a n互质  我们就根据欧拉定理降幂

                 (mod n)

如果不互质   我们就根据扩展欧拉定理降幂

                  我们在求  % n  的时候 可以通过判断  来转成上面的两个式子之一

欧拉函数代码实现：

最简单最慢的写法：

int Euler(int x)
{
    int res=x;
    for(int i=2;i<sqrt(x)+1;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)
                x/=i;
        }
    }
    if(x>1)
        res=res/x*(x-1); //本身是素数
    return res;
}

递推求法，求1~n的欧拉函数

int phi[N];
void Euler()
{
    for(int i=1;i<=N;i++)
        phi[i]=i;
    for(int i=2;i<=N;i++)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=N;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

线性筛法（看起来好难~）

int phi[N],prime[N];  
bool v[N];  
void Euler(int n)  
{  
    int cnt=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])  
        {
            prime[++cnt]=i;//存储素数i
            phi[i]=i-1;//当i是素数时phi[i]=i-1  
        }
        for(j=1;j<=cnt;j++)
        {
            if(i*prime[j]>N)
                break;
            v[i*prime[j]]=1; //确定i*prime[j]不是素数
            if(i%prime[j]==0)//看prime[j]是否是i的约数  
            {  
                phi[i*prime[j]]=phi[i]*prime[j];
                break;  
            } 
            else  
                phi[i*prime[j]]=phi[i]*(prime[j]-1);//其prime[j]-1就是phi[prime[j]]，利用了欧拉函数的积性  
       }  
   }  
}