欧拉函数
欧拉函数简单介绍
对一个正整数n，欧拉函数是求小于或等于n的正整数中与n互质的数的数目
举个例子
对于 在小于等于8的数中，1 3 5 7分别与8互质
欧拉函数公式
(其中p1, p2……pn为x的所有质因数，x是不为0的整数)
定义 φ(1)=1（和1互质的数(小于等于1)就是1本身）。
性质
若n是质数p的k次幂，因为除了p的倍数外，其他数都跟n互质。
欧拉函数是积性函数——若m,n互质，
特殊性质：当n为奇质数时,, 证明与上述类似。
若n为质数则
https://blog.csdn.net/yuyanggo/article/details/50389919
板子
腾讯公司福利 1138人发布