(以下p表示质数)

①当n = p^k时：  

②若m,n互质：

③n为质数时： 

④对任何两个互质的正整数a, m(m>=2)有

 即欧拉定理

当m是质数p时，此式则为：

 即费马小定理

⑤所有小于n并且与n互质数的和为：sum = n * φ(n)/2

⑥如果 i mod p=0,其中p为质数,则 φ(i∗p)=p∗φ(i),否则φ(i∗p)=(p−1)φ(i)

模板

bool vis[N]; //质数为0 int prime[N], phi[N]; //一个存质数，一个是欧拉函数 void get_prime(){ int pos = 0; phi[1] = 1; vis[1] = 1; for(ll i = 2; i <= N; i++){ if(!vis[i]){ prime[++pos] = i; phi[i] = i-1; } for(ll j = 1; j <= pos && prime[j]*i <= N; j++){ vis[i*prime[j]] = 1; if(i%prime[j] == 0){ phi[i*prime[j]] = phi[i]*prime[j]; break; } phi[i*prime[j]] = phi[i]*phi[prime[j]]; } } }

 

转载于:https://www.cnblogs.com/philo-zhou/p/11366319.html

相关资源：JAVA上百实例源码以及开源项目