7.21
今天DTZ大爷教了我一个算欧拉函数的好方法......是质因数复杂度的
这让我想到，这些小技巧小idea，很多时候，可能就是考场上最致命、最一击必杀的“大招”
因此开个坑记录一下，定有好处
欧拉函数的意义是比一个数小的数中有多少个和它互质的，不要考场上想到了这句话想不到欧拉函数
然后是求欧拉函数的一个方法
设一个数\(x=\prod_{i=1}^{k}p_i^{a_i}\)，那么：
\(\varphi(x)=\prod_{i=1}^{k}(p_i-1)p_i^{a_i-1}=x\prod_{i=1}^{k}\frac{p_i-1}{p_i}\)
原文：https://www.cnblogs.com/dedicatus545/p/9347817.html