AcWing 874. 筛法求欧拉函数 - AcWing

Loading [MathJax]/jax/output/HTML-CSS/jax.js

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 874. 筛法求欧拉函数原题链接简单

作者：

Sundae , 2020-01-19 12:46:41 , 所有人可见 , 阅读 3577

82

39

首先欧拉函数是一个积性函数就是说 m,n互素则
$\varphi(mn) = \varphi(m)*\varphi(n)$

如果X 是一个素数P
$x = p \quad \varphi(x) = x *(1 - \frac{1}{p}) = p * (\frac{p - 1}{p}) = p -1$
不是素数的时候用最小的素因子去计算
$i \% p=0\quad gcd(i, p) = p\quad\varphi(i) = i * (1 - \frac{1}{p_1}) * … * (1 - \frac{1}{p_k})\\\\因为p是i的因子所以在计算\varphi(i)的已经算过p了\\ \varphi(i * p) = p * i * (1 - \frac{1}{p_1}) * … * (1 - \frac{1}{p_k}) \\ \varphi(i * p) = p * \varphi(i)$

当 i 和 p 互质的时候

$i \% p != 0\quad gcd(i, p) = 1\\ \varphi(i * p) = \varphi(i) * \varphi(p) = \varphi(i) * (p -1)$

16 评论

Zzint 2022-09-30 10:32

回复

tql大佬数学这块每次看你证明题解马上就懂了

Sundae 2022-09-30 16:20

回复

谢谢～

Sundae 2020-01-19 18:28

回复

补充如果gcd(m, n) = d 则 $\varphi(m*n) = \varphi(m) * \varphi(n) * \frac{d}{ \varphi(d)}$

Akko__ 2021-05-29 12:00

回复

555, 太感谢了，之前一直有个点看不懂，看到这个公式秒懂

Sundae 2021-05-29 15:57 回复了 Akko__ 的评论

回复

谢谢～～

大伟老师的亲传弟子 2022-07-07 09:16

回复

这个公式是怎么来的呀，orz

lklk 2022-12-01 15:19

回复

tql大佬，看了一遍y总的有点迷迷糊糊的，看了大佬的一下子顿悟了！

霾 2022-12-12 15:21

回复

tql大佬，看了一遍lk的笔记有点迷迷糊糊的，看了大佬的一下子顿悟了！

lsp_同学 2022-10-24 22:34

回复

第一句话让人豁然开朗

探店鞲夶多真假厨子说诸王峡谷三人188 2022-09-02 16:07

回复

非常清晰啊

初静 2021-02-05 21:10

回复

您写的很棒，谢谢~！

Sundae 2021-02-06 15:49

回复

谢谢～～～

初静 2021-02-05 21:03

回复

gcd 在这里指的是最大公约数吗？

Sundae 2021-02-06 15:49

回复

是的 gcd指的是最大公约数 lcm指的是最小公倍数

zzw1 2020-01-19 23:37

回复

这么漂亮的公式怎么写的

Sundae 2020-01-20 14:12

回复

Latex 呀 hhh 在本地写好然后复制过来

1024

x