目录

• 数论基础——欧拉函数
• 定义
• 通式
• 代码
• 性质

数论基础——欧拉函数

定义

对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

通式

$\varphi(n)=n\times(1-1/p_1)\times(1-1/p_2)\times(1-1/p_3)\times...\times(1-1/p_n)$φ(n)=n×(1−1/p1​)×(1−1/p2​)×(1−1/p3​)×...×(1−1/pn​)
即：$\varphi(n)=n\times\prod_{i=1}^{n}{\frac{p_i-1}{p_i}}$φ(n)=n×∏i=1n​pi​pi​−1​
$p_1、p_2、p_3...p_n$p1​、p2​、p3​...pn​是n（n>0）的质因数.
注意：$\varphi(1)=1$φ(1)=1.

代码

ll eular(ll n)
{
    ll ans = n;
    for(int i=2; i*i <= n; i++)
    {
        if(n%i == 0)//i是质因数
        {
            ans = ans/i*(i-1);
            while(n%i == 0)//确保不会出现合数因子
                n/=i;
        }
    }
    if(n > 1) ans = ans/n*(n-1);
    //因为i是从2开始，所以上面的循环无法判断n是素数的情况，因此在这加个判断
    return ans;
}

性质

1.若p为质数，$\varphi(p)=p-1$φ(p)=p−1

2.若m,n互质，则$\varphi(m\times n)=\varphi(m)\times\varphi(n)$φ(m×n)=φ(m)×φ(n)

3.若$n=p^k(p是质数)$n=pk(p是质数)，则$\varphi(n)=(p-1)\times p^{k-1}$φ(n)=(p−1)×pk−1

4.欧拉定理：对于互质的m、n，有$n^{\varphi(m)}≡1(mod m)$nφ(m)≡1(modm)

5.费马小定理：对于质数p
若n mod p = 0 ，则 $φ(n\times p)=φ(n)\times p$φ(n×p)=φ(n)×p
若n mod p ≠ 0 ，则$φ(n\times p)=φ(n)\times (p-1)$φ(n×p)=φ(n)×(p−1)

6.小于n且与n互质的数的和：$S=n\times \frac{\varphi(n)}{2}$S=n×2φ(n)​

7.$n=∑_{d|n}φ(d)$n=∑d∣n​φ(d)
注： (d|n)指n是d的倍数

• 点赞
• 收藏
• 分享
• • 文章举报

sqi_王 发布了10 篇原创文章 · 获赞 1 · 访问量 177 私信 关注