【数论】欧拉函数
WeLikeStudying · · 个人记录
简单的介绍
- 其中
[a]=\begin{cases}1&a\text{ is true}\\0&a\text{ is false}\end{cases} 。 - 这是一个积性函数。
- 显然对于
k>0 ，\varphi(p^k)=p^k-p^{k-1}=(p-1)p^{k-1} 。 - 所以可以线性筛
O(n) 求前n 个欧拉函数。 - 当然也同时揭示：
\varphi(n)=n\prod_{i}{\frac{p_i-1}{p_i}}
奇怪的问题
- 小问题：如何求：
\sum_{i\bot n}i - 注意到：
i\bot n\Leftrightarrow (n-i)\bot n - 所以答案为
\frac{n\varphi(n)}2 。 - 不过要特判
n=1 。 - 小问题：对于数列
\lbrace a_n\rbrace 满足a_0=n,a_{i+1}=\varphi(a_i) ，大概第几个数为变成 1 。 - 冷知识：除了 1,2 的所有整数，它的欧拉函数值都是偶数，因为它要么是二的高次幂，要么有奇质数因子。
- 显然偶数的欧拉函数至少比原来小一半。
- 所以大概第
\log_2(n) 个数会第一个变成 1 。 - 重要知识：
\varphi\times1=i_1 。 - 也就是：
n=\sum_{d|n}\varphi(d) - 证明:
\sum_{d|n}\varphi(d)=\sum_{d|n}\varphi(\frac nd) - 而
\varphi(\frac nd) 的意义是[1,n] 中与n 的最大公约数为d 的数的个数。 - 所以所以式子成立。
高级的函数
- 乔丹函数（？）
J_k(n)=n^k\prod_{i}{\frac{p_i^k-1}{p_i^k}} - 意义是
[1,n] 中选k 个数，满足它们和 n 一起\gcd 的结果为 1 。 -
内积
- 求
\varphi(n\cdot m) ？ - 是
\varphi(\frac n{\gcd(n,m)})\varphi(\gcd^2(n,m))\varphi(\frac m{\gcd(n,m)}) 吗。 - 显然不行，因为
\dfrac n{\gcd(n,m)}\bot\gcd^2(n,m) 显然不一定成立（这个式子的性质其实不错）。 - 考虑
\varphi(n)\cdot\varphi(m) 导致其无效的部分是。\prod_{p_i|n,p_i|m}{\bigg(\frac{p_i-1}{p_i}\bigg)}^2 - 而本来应该是：
\prod_{p_i|n,p_i|m}{\frac{p_i-1}{p_i}} - 先除
\varphi(\gcd(n,m)) 多除了\gcd(n,m) ，再把它乘上去。 - 即：
\varphi(n\cdot m)=\frac{\varphi(n)\cdot\varphi(m)\cdot\gcd(n,m)}{\varphi(\gcd(n,m))} - 例题。
拓展函数
假如我们想要求与
显然