警告
本文最后更新于 2023-07-07，文中内容可能已过时。
欧拉函数是求小于 x 并且和 x互质 的数的个数
通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn)
其中 p1, p2……pn 为 x 的所有质因数，x 是不为 0 的整数
φ(1)=1（唯一和 1 互质的数就是 1 本身）【注意：每种质因数只一个。比如 12=223】
定理：
- 若 n 是素数 p 的 k 次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了 p 的倍数外，其他数都跟 n 互质
- 欧拉函数是积性函数——若 m,n 互质，φ(mn)=φ(m)φ(n)
特殊性质：
- 当 n 为奇数时，φ(2n)=φ(n)
- p 是素数，φ(p) = p - 1，φ(p) 称为 p 的欧拉值
- 若 a 为素数，b mod a=0,
φ(a*b)=φ(b)*a
模板
//直接法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int Euler(int n){
int res = n,i;
//由于任何一个合数都至少有一个不大于根号 n 的素因子，所以只要遍历到根号 n 即可
for(i=2;i * i <= n;i++)
if(n%i == 0){ //第一次找到的必为素因子
n /=i ;
res = res - res/i; //x(1-1/p1)
while(n % i ==0)
n/=i; //将该素因子的倍数也全部筛掉
}
if (n > 1)
res = res - res/n;
return res;
}
|
以上转载注明
//素数筛选法，先素数筛选，再求欧拉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| /*
特性 :
1. 若 a 为质数，phi[a]=a-1;
2. 若 a 为质数，b mod a=0,phi[a*b]=phi[b]*a
3. 若 a,b 互质，phi[a*b]=phi[a]*phi[b](当 a 为质数时，if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
*/
int m[n],phi[n],p[n],nump;
//m[i] 标记 i 是否为素数，0 为素数，1 不为素数；p 是存放素数的数组；nump 是当前素数个数；phi[i] 为欧拉函数
int make()
{
phi[1]=1;
for (int i=2;i<=n;i++)
{
if (!m[i])//i 为素数，m[] 初始化为 0
{
p[++nump]=i;//将 i 加入素数数组 p 中
phi[i]=i-1;//因为 i 是素数，由特性得知
}
for (int j=1;j<=nump&&p[j]*i<n;j++) //用当前已的到的素数数组 p 筛，筛去 p[j]*i
{
m[p[j]*i]=1;//可以确定 i*p[j] 不是素数
if (i%p[j]==0) //看 p[j] 是否是 i 的约数，因为素数 p[j], 等于判断 i 和 p[j] 是否互质
{
phi[p[j]*i]=phi[i]*p[j]; //特性 2
break;
}
else phi[p[j]*i]=phi[i]*(p[j]-1); //互质，特性 3,p[j]-1 就是 phi[p[j]]
}
}
}
|
附素数打表
1
2
3
4
5
6
7
8
9
10
| int p[N]={1,1,0};
void prime(){
for(int i=2;i<N;i++)
if(!p[i]){
for(int j=2*i;j<=N;j+=i)//筛掉 i 的倍数
p[j]=1;
}
}
|
例题
Bi-shoe and Phi-shoe LightOJ - 1370
题意：
给一些数 Ai（第 i 个数），Ai 这些数代表的是某个数欧拉函数的值，我们要求出数 Ni 的欧拉函数值不小于 Ai。而我们要求的就是这些 Ni 这些数字的和 sum，而且我们想要 sum 最小，求出 sum 最小多少。
解题思路：
要求和最小，我们可以让每个数都尽量小，那么我们最后得到的肯定就是一个最小值。
给定一个数的欧拉函数值 ψ(N)，我们怎么样才能求得最小的 N?
我们知道，一个素数 P 的欧拉函数值 ψ(P)=P-1。所以如果我们知道 ψ(N)，那么最小的 N 就是最接近 ψ(N)，并且大于 ψ(N) 的素数。我们把所有素数打表之后再判断就可以了。
这个 lightoj 有毒，什么头文件都不支持，卡了我好久。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<stdio.h>
#define N 1000005
#define ll long long
int m[N]={1,1,0};
int p[100000],cnt=0;
int max(int x,int y){
return x>y?x:y;
}
void prime(){
for(int i=2;i<N;i++)
if(!m[i]){
for(int j=2*i;j<=N;j+=i)
m[j]=1;
p[cnt++]=i;
}
}
int binary_search(int x){//二分查找
int l=0,r=cnt;
while(l<=r){
int mid=(l+r)/2;
if(p[mid]>x)
r=mid-1;
else l=mid+1;
}
for(int i=max(r,0);;i++)
if(p[i]>x)
return p[i];
}
int main(){
prime();
int T,n,cas=1,temp;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
ll sum=0;
for(int i=0;i<n;i++){
scanf("%d",&temp);
sum+=binary_search(temp);
}
printf("Case %d: %lld Xukha\n",cas++,sum);
}
return 0;
}
|
Jian YE
支付宝
微信