欧拉函数
对于正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目，记作φ(n).
φ(1)=1
求n的欧拉值
首先， 欧拉函数是一个积性函数，当m,n互质时，φ(mn)=φ(m)∗φ(n)
根据唯一分解定理知 n=pa11∗pa22∗…∗paxx
因此 φ(n)=φ(pa11)∗…∗φ(paxx)
对于任意一项 φ(pass)=pass−p(as−1)s
从定义出发 φ(pass)等于小于或等于pass的正整数中与pass互质的数的数目
从1到pass中共有pass个数字
其中与pass不互质的有ps,2ps,…,psas−1∗ps ,共psas−1项
所以 φ(pass) = pass - psas−1=pass∗(1−1ps)
因此
φ(n)=φ(pa11)∗…∗φ(paxx)
=(pa11−p1a1−1)∗…∗(paxx−pxax−1)
=pa11∗(1−1p1)∗pa22∗(1−1p2)∗…∗paxx∗(1−1px)
=pa11∗pa22∗…∗paxx∗(1−1p1)∗(1−1p2)∗…∗(1−1px)
=n∗x∏i=1(1−1pi)
我懂了，就是n可以写成几个素数幂相乘，而根据互质原理与n互质数的数量正好等于几个素数分别求各自互质数的数量然后相乘，此时呢每个乘数又是 素数的几次方(p的 β次幂)所以不和他互质的数量就是p的倍数 就是从p到p的β次幂个所以互质的个数就是p的β次幂减去p的β-1次幂个就是p的β乘于(1-1/p)。。。。。。。
n可以写成几个素数幂相乘 是 唯一分解定理。
对于数字n而言， 这若干的素数幂是确定且唯一的。
# ▄█▀█●
▄█▀█●
# ▄█▀█●
互质 指的是两个数的最大公约数是1
# ▄█▀█●
# ▄█▀█●
哭哭，好复杂，看到一堆数学公式就晕。还是手动模拟一遍，记个答案吧😣 😣
加油~ 这个公式还是比较好理解的~
这个公式不就是先去掉所有p1的倍数,在筛过p1的基础上,即N*(1-1/p1).再对剩余的整体进行筛选,即乘上(1-1/p2)等等等。是我理解错了吗hh。感觉一点也不难啊，哪位大佬指点我一哈
是的
为什么欧拉函数式一个积性函数？
https://zhuanlan.zhihu.com/p/394427565
\huge ▄█▀█●
▄█▀█●
▄█▀█●
秒呀
硬核
醍醐灌顶~
GG Bond想妈妈了o(╥﹏╥)o
▄█▀█●
▄█▀█●
orz
厉害厉害
# ▄█▀█●
▄█▀█●
为什么φ(n)=φ(pa11)∗…∗φ(paxx)？