欧拉函数

• 定义
  对于正整数n小于等于n的数中与n互质的数的个数记为$\varphi(n)$,即为欧拉函数
• 欧拉公式
  由算数基本定理任意一个正整数都可以写作n=$p_1^{a_1}p_2{a_2}\cdots p_k^{ak}$
  那么$\varphi(n)=n\prod\limits_{i=1}^{k}({1-\frac{1}{p_i}})$
• 数学证明
  首先$\varphi(n)$是一个积性函数
  即 $\varphi(a_1a_2)=\varphi(a_1)\varphi(a_2)$这个的证明这里不作叙述可看这个链接积性证明
  然后从1到一个数$p_n^{{a_n}$一共有$p_n}{a_n}$个数其中与其不互质的有$p_n,2p_n,3p_n\dots p_n^{a_n}(p_n{a_{n-1}}p_n)$一共有$p_n^{{a_{n-1}}$个数，所以与其互质的一共有$p_n}{a_n}(1-\frac{1}{p_n})个$
  所以有：
  $$
  \varphi(n)=\varphi(p_1^{{a_1})*\varphi(p_2}{a_2})\dots\varphi(p_k^{a_k})\
  =p_1^{{a_1}(1-\frac{1}{p_1})*p_2}{a_2}(1-\frac{1}{p_2})\dotsp_k^{{a_k}\=n*\prod\limits_{i=1}}{k}(1-\frac{1}{p_i})
  $$
• 代码实现

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a;
        scanf("%d",&a);
        int res=a;
        for(int i=2;i<=a/i;i++)
        {
            if(a%i==0)
            {
                res=res/i*(i-1);//注意先除再乘防止爆int
            }
            while(a%i==0)
            {
                a/=i;
            }
        }
        if(a>1)
        {
            res=res/a*(a-1);
        }
        printf("%d\n",res);
    }
    
    
    return 0;
}

• 代码细节
  注意res=res/i*(i-1)这里要先除再乘防止爆int 可能会有疑问我们推导的公式中$1-\frac{1}{p_i}$是一个小数但是c++里/是向下取整的，那么这里会不会有问题呢?其实是完全没问题的 我们可以看到只有当a%i==0时我们才会进行res的操作并且每次循环中a至少都和res除i除的一样多也就是说只要a中有约数 i 那么res中也一定有 i 一定不会出现小数。

Written with StackEdit中文版.