(以下 p 表示质数)
1当 n = p^k 时:
2若 m,n 互质:
3n 为质数时:
4对任何两个互质的正整数 a, m(m>=2) 有
即欧拉定理
当 m 是质数 p 时, 此式则为:
即费马小定理
5所有小于 n 并且与 n 互质数的和为: sum = n * φ(n)/2
模板
- 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]];
- }
- }
- }
来源: http://www.bubuko.com/infodetail-3158508.html