欧拉函数是求小于 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 49 | #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 Xukhan",cas ,sum); } return 0; } |
|---|
