φ(m)

1
2
表示不大于m中与m互素的数的个数
显然 φ(p)=p-1 。

积性函数

f(x)有性质:对任意互质整数m和n ,有f(mn

)=f(m)*f(n)

(完全积性函数:对于任意整数都有上式成立)
在这里插入图片描述

_❤φ(m)是一个积性函数!!_

线性筛求欧拉函数

通过这个性质我们得到了欧拉函数的求解方法:

1
2
3
4
5
6
7
8
9
10
11
12
int getphi(int n){
int m=sqrt(n+0.5);
int ans=n;
for (int i=2;i<=m;i++){
if (n%i ==0 ){
ans=ans/i*(i-1);
while (n%i == 0) n/=i;
}
}
if (n>1) ans=ans*n*(n-1);
return ans;
}

以及线性求1~n欧拉函数值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int tot=0;
int phi[maxn],prime[maxn];
bool isPrime[maxn];
void getphi(){
mem(isPrime,true);//宏
phi[1]=1;
for(int i=2;i<=maxn;i++){
if(isPrime[i]) prime[++tot]=i,phi[i]=i-1;//*
for(int j=1;j<=tot;j++){
if(i*prime[j]>maxn) break;
isPrime[i*prime[j]]=false;
if(i%prime[j]==0){
//如果pt不是在ipt中第一次出现的话(也就是pt整除i)
phi[i*prime[j]]=phi[i]*prime[j];
break;

}else
//如果pt是在ipt中第一次出现的话(也就是pt不整除i)
phi[i*prime[j]]=phi[i]*(prime[j]-1);

}
}
}

在这里插入图片描述
费马小定理:
在这里插入图片描述