欧拉函数:
- 欧拉函数定义:
1~n中与n互质的数的个数。 比如
- 欧拉函数是积性函数:(也就是)当 n与m互质的时候:
- 由算术基本定理,我们可以设n=
,那么我们只要计算出
的取值就能求出
的取值。 下面给出证明
的取值怎么求? 也就是求1~
中与
互质的数的个数
我们可以求与
不互质的数的个数,由于p是质数,所以与
不互质的数一定是p的倍数
那么1~
中,p的倍数就是
, 那么我们就知道与
不互质的数的个数 就是
。也就是
由于
之间互质,且欧拉函数是一个积性函数,那么有
所以我们只需要求出n的所有质因子p,然后求出 的乘积即可
phi = n;
for(int i=2 ; i*i<=n ; i++ )
if( n%i == 0 ){
phi = phi/i * (i-1 ) // 1- 1/p == (p-1)/p 为了防止爆int,故意不写成phi*(i-1)/i
while ( n%i==0 ) n/=i ;
}
if(n!=1) phi =phi/n *(n-1); //防止n有一个大于 sqrt(n)的质因子的情况
以上就是欧拉函数的板子,请牢牢记住,后面回经常用到。