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