CSDN

欧拉函数证明与代码实现

2023-06-28 22:48 由 Taco_gu 发表于 #其他

欧拉函数

  • 定义
    对于正整数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中文版.

热门相关：总裁别再玩了   天神诀   前任无双   天神诀   花月颂