标签：frac 函数 int res 代码 varphi 互质 欧拉

欧拉函数

• 定义
  对于正整数n小于等于n的数中与n互质的数的个数记为\(\varphi(n)\),即为欧拉函数
• 欧拉公式
  由算数基本定理任意一个正整数都可以写作n=\(p_1^{a_1}p_2^{a_2}\cdots p_k^{a^k}\)
  那么\(\varphi(n)=n\prod\limits_{i=1}^{k}({1-\frac{1}{p_i}})\)
• 数学证明
  首先\(\varphi(n)\)是一个积性函数
  即 \(\varphi(a_1*a_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})\dots*p_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中文版.

标签：frac,函数,int,res,代码,varphi,互质,欧拉
From： https://www.cnblogs.com/Taco-gu/p/17512777.html