首先 欧拉函数是一个 积性函数 就是说 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) $$
tql大佬 数学这块每次看你证明题解马上就懂了
谢谢～
补充 如果
gcd(m, n) = d则 $\varphi(m*n) = \varphi(m) * \varphi(n) * \frac{d}{ \varphi(d)} $555, 太感谢了，之前一直有个点看不懂，看到这个公式秒懂
谢谢～～
这个公式是怎么来的呀，orz
tql大佬，看了一遍y总的有点迷迷糊糊的，看了大佬的一下子顿悟了！
tql大佬，看了一遍lk的笔记有点迷迷糊糊的，看了大佬的一下子顿悟了！
第一句话让人豁然开朗
非常清晰啊
您写的很棒，谢谢~！
谢谢～～～
gcd 在这里指的是最大公约数吗？
是的 gcd指的是最大公约数 lcm指的是最小公倍数
这么漂亮的公式怎么写的
Latex 呀 hhh 在本地写好 然后复制过来