写这个类型博客的目的就是想总结一下某个专题的知识点，方便以后比赛前复习，由于太菜，如有错误，还请斧正。

首先我们要区别欧拉函数和欧拉定理

欧拉定理简单来说是用于求逆元的，当然也可用于降幂运算（若a，n互质 a^k ≡ a^(k mod φ(n)) (mod n) ）

至于扩展欧拉定理就不在这讲述了（主要太菜，不理解，如有需要的可以进入这个链接：https://zhuanlan.zhihu.com/p/24902174）

接下来我们来说说今天的主角：欧拉函数

欧拉函数有什么用呢？

  1. 求1~n内与n互质的数的个数，直接就是φ。
  2. 求1~n内与n互质的数的总和，就是n * φ(n)/2；（1~n内与n互质的数具有对称性，即gcd(x,n)=1,则gcd(n-x,n)=1）

那么如何求欧拉函数？

(这是通项公式）

常用的求导欧拉函数方式：

1.欧拉筛求导欧拉函数

for(i=1;i<=n;i++)
{
    if(prime[i]) //判断是否质数
    {
        phi[i] = i-1;
        num++;
        zs[num] = i;
    }
    //筛质数顺便求解
    for(j=1;i*zs[j]<=n && j<=num;j++)
    {
        prime[i*zs[j]] = false;
        if(i%zs[j]!=0) phi[i*zs[j]] = phi[i]*phi[zs[j]];
            else phi[i*zs[j]] = phi[i]*zs[j];
    }
}

2.埃氏筛求导欧拉函数

void euler(int n)
{
    for (int i=1;i<=n;i++) phi[i]=i;
    for (int i=2;i<=n;i++)
    {
        if (phi[i]==i)//这代表i是质数
        {
            for (int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);//把i的倍数更新掉
            }
        }
    }
}

接下来，我们来讲讲欧拉函数的性质（参考https://blog.csdn.net/liuzibujian/article/details/81086324）

  1. 对于质数，
  2. 若p为质数,则
  3. 若m、n互质，则
  4. 当n>2时是偶数
  5. 小于n的数中，与n互质的数的总和为：
  6. n的因数（包括1和它自己）的欧拉函数之和等于n