首先 欧拉函数是一个 积性函数 就是说 m,n互素 则
φ(mn)=φ(m)∗φ(n)
如果X
是一个素数P
x=pφ(x)=x∗(1−1p)=p∗(p−1p)=p−1
不是素数的时候 用最小的素因子去计算
i%p=0gcd(i,p)=pφ(i)=i∗(1−1p1)∗…∗(1−1pk)因为p是i的因子所以在计算φ(i)的已经算过p了φ(i∗p)=p∗i∗(1−1p1)∗…∗(1−1pk)φ(i∗p)=p∗φ(i)
当 i 和 p 互质的时候
i%p!=0gcd(i,p)=1φ(i∗p)=φ(i)∗φ(p)=φ(i)∗(p−1)
tql大佬 数学这块每次看你证明题解马上就懂了
谢谢~
补充 如果
gcd(m, n) = d
则 φ(m∗n)=φ(m)∗φ(n)∗dφ(d)555, 太感谢了,之前一直有个点看不懂,看到这个公式秒懂
谢谢~~
这个公式是怎么来的呀,orz
tql大佬,看了一遍y总的有点迷迷糊糊的,看了大佬的一下子顿悟了!
tql大佬,看了一遍lk的笔记有点迷迷糊糊的,看了大佬的一下子顿悟了!
第一句话让人豁然开朗
非常清晰啊
您写的很棒,谢谢~!
谢谢~~~
gcd 在这里指的是最大公约数吗?
是的 gcd指的是最大公约数 lcm指的是最小公倍数
这么漂亮的公式怎么写的
Latex 呀 hhh 在本地写好 然后复制过来