欧拉函数算法实现_编程代码

1.欧拉函数

φ(n)：1~n内，与n互质的数的个数
φ(6)=2，1 2 3 4 5 6

任意正整数n： $n=p_1^{a_1}{p}_2^{a_2}...p_m^{a_m}$ ( $p_i$ 为素数)
欧拉函数计算公式：$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$
证明：（容斥原理）
1.从1~n中去掉$p_1、p_2、...、p_m$的所有倍数（剩余个数 $N_1=n-\frac{n}{p_1}-\frac{n}{p_2}-...-\frac{n}{p_m}$）
2.加上所有$p_i\ast p_j$的倍数（$N_2=N_1+\frac{n}{p_1\ast p_2}+\frac{n}{p_1\ast p3}+...+\frac{n}{p_2\ast p_3}+...\frac{n}{p_{n-1}\ast p_n}$）
3.减去所有$p_i\ast p_j\ast p_k$的倍数（$N_3=N_2-\frac{n}{p_1\ast p_2\ast p_3-...}$）
…
进行算术处理后，就会知道$(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_m})$展开后就会是上述容斥原理所要求的式子。

时间复杂度分析：

通过上式直接进行计算，算法的时间复杂度瓶颈在于分解质因数O(√n)。

例题

输入

3 3 6 8 

输出

2 2 4 

代码

$O(n{\sqrt{a}}_i)$ ——> $4\ast 10^6$~$5\ast 10^6$

#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> const int maxn=2010; const int mod=1e9+7; using namespace std; int phi(int x) { 
    int ans=x; for(int i=2;i<=x/i;i++) if(x%i==0) { 
    ans=ans/i*(i-1); while(x%i==0) x/=i; } if(x>1) ans=ans/x*(x-1); return ans; } int main() { 
    int n; cin>>n; while(n--) { 
    int x; cin>>x; cout<<phi(x)<<endl; } return 0; } 

2.筛法求欧拉函数 O(n)

如果我们要求出1~n中每一个数的欧拉函数，如果我们还是用公式去算，那么我们一个个去分解质因数就很慢，整个程序时间复杂度就是O(n√n)，所以要用筛法。

例题

primse[j]是否在i中出现过 只跟质因子有关，跟质因子出现的次数无关

i%primes[j]==0
$\phi (i)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})...(1-\frac{1}{p_k})$ pj出现过
$\phi (p_j\ast i)=p_j\ast i\ast (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})...(1-\frac{1}{p_k})=p_j\ast \phi (i)$

i%primes[j]!=0

$\phi (i)=i(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$
$\phi (p_j\ast i)=p_j\ast i\ast (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})(1-\frac{1}{p_j})=p_j\ast \phi (i)\ast (1-\frac{1}{p_j})=\phi (i)\ast (p_j-1)$

#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> const int maxn=1e6+5; const int mod=1e9+7; using namespace std; int primes[maxn],euler[maxn],cnt; bool st[maxn]; void get_eulers(int n) { 
    euler[1]=1; for(int i=2;i<=n;i++) { 
    if(!st[i]) { 
    primes[cnt++]=i; euler[i]=i-1;//质数的欧拉函数除掉它本身 } for(int j=0;primes[j]<=n/i;j++) { 
    int k=primes[j]*i; st[k]=true; if(i%primes[j]==0) { 
    euler[k]=euler[i]*primes[j]; break; } euler[k]=euler[i]*(primes[j]-1); } } } int main() { 
    int n; cin>>n; get_eulers(n); long long sum=0; for(int i=1;i<=n;i++) sum+=euler[i]; cout<<sum<<endl; return 0; } 

3.欧拉定理

若a和n互质，则有$a^{\phi (n)}\equiv 1modn$
eg. a=5，n=6，则φ(6)=2，$a^{\phi (n)}=25$，25%6=1，1%6=1

简要证明

假设1~n中，与n互质 的数有$a_1,a_2,...a_{\phi (n)}$
因为a和n互质，提出a，$a^{\phi (n)}(a_1,a_2,...a_{\phi (n)})\equiv a_1,a_2,...a_{\phi (n)}(modn)$

        ——>$a^{\phi (n)}\equiv 1(modn)$

所以$a{a}_1,a{a}_2,...a{a}_{\phi (n)}$在mod n的情况下和上述$a_1,a_2,...a_{\phi (n)}$在mod n的情况下是相等的

4.费马小定理

若p为质数，且由欧拉定理有 $a^{\phi (p)}\equiv 1modp$，$\phi (p)=p-1$=>费马定理：

若正整数a与素数p互质，则有$a^{p-1}\equiv 1(modp)$,或写为$a^p\equiv a(modp)$

费马小定理求逆元

若p为素数，且(a,p)=1，$a^{p-1}\equiv 1(modp)$ → $a{a}^{p-2}\equiv 1(modp)$，a的逆元就是$a^{p-2}$

欧拉定理求逆元

若a,p互素，$a^{\phi (p)}\equiv 1(modp)$ → $a{a}^{\phi (p)-1}\equiv 1(modp)$

5.快速幂

例题

计算范围可达到10^9

a^k，朴素做法循环一遍，时间复杂度O(k)

int ans=1; for(int i=1;i<=k;i++) { 
    ans=ans*a%p; } 

如果用快速幂的话，logk->30左右

算法原理：

预处理出 $a^{2^0}modp$，$a^{2^1}modp$，…，$a^{2^{logk}}modp$这logk个值

$a^k=a^{2^i}\ast a^{2^j}\ast a^{2^m...}=a^{2^i+2^j+2^m+...}$，就是要把指数拆成二进制表示。

$a^{2^0}$  ——>  $a^1=a$
$a^{2^1}$  ——>  $=a^{2^0\ast 2=(a^{2^0}{)}^2}$
$a^{2^2}$  ——>  $=a^{2^1\ast 2=(a^{2^1}{)}^2}$
…
$a^{2^{logk}}$  ——>  $a^{2^{logk-1}\ast 2=(a^{2^{logk-1}}{)}^2}$

eg. $4^{5}mod10$

$4^{2^0}\%10=4$
$4^{2^1}\%10=6$
$4^{2^2}\%10=6$

$4^5=4^{(101{)}_2}=4^{2^0+2^2}=4^{2^0}\ast 4^{2^2}=(4\ast 6)\%10=4(\%10)$

时间复杂度分析：

预处理部分logk个数，拆分成的二进制表示这步也是logk个，所以总的时间复杂度就是O(logk)

#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> const int maxn=1e6+5; const int mod=1e9+7; typedef long long ll; using namespace std; long long quick_pow(int a,int b,int p) { 
    long long res=1%p;//一定要注意要这样初始化,因为当p=1时，结果就会不同了，1%1=0 while(b) { 
    if(b&1)//当前位数是1，就乘到结果上 res=res*1ll*a%p;//第一次就是a^{2^0} a=a*1ll*a%p;//平方一下 b>>=1;//右移一位 } return res; } int main() { 
    int n; scanf("%d",&n); while(n--)//数据量有点大，建议用scanf { 
    int a,k,p; scanf("%d%d%d",&a,&k,&p); printf("%lld\n",quick_pow(a,k,p)); } return 0; } 

5.快速幂求逆元

对于整数a,n,如果有gcd(a,n)=1,那么就存在一个整数x使得 ax=1(mod n)，x即为a的逆元

性质

$\frac{a}{b}\equiv a\ast b^{-1}(modm)$

$b\ast \frac{a}{b}\equiv b\ast a\ast b^{-1}(modm)$

$a\equiv b\ast a\ast b^{-1}(modm)$，又a和m互质，所以有

$b\ast b^{-1}\equiv 1(modm)$

eg. b=3，m=5，求b%m的逆元 2   (3*2)%5=1

逆元为 $3^{5-2}=3^3=27\%5=2$

例题

输入

3 4 3 8 5 6 3 

输出

1 2 impossible 

费马小定理求逆元

若p为素数，且a,p互质，$a^{p-1}\equiv 1(modp)$ → $a{a}^{p-2}\equiv 1(modp)$，a的逆元就是$a^{p-2}$

#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> const int maxn=1e6+5; const int mod=1e9+7; typedef long long ll; using namespace std; ll quick_pow(int a,int b,int p) { 
    ll res=1%p;//一定要注意要这样初始化,因为当p=1时，结果就会不同了，1%1=0 while(b) { 
    if(b&1) res=res*1ll*a%p;//第一次就是a^{2^0} a=a*1ll*a%p;//平方一下 b>>=1;//右移一位 } return res; } int main() { 
    int n; scanf("%d",&n); while(n--)//数据量有点大，建议用scanf { 
    int a,p; scanf("%d%d",&a,&p); if(a%p!=0) printf("%lld\n",quick_pow(a,p-2,p)); else printf("impossible\n"); } return 0; } 

a是p的倍数的时候是无解的 a*x%p=0，不可能模p等于1

由于a不是p的倍数，且p是质数，所以a和p一定互质，由费马定理 $b^{p-1}\%p\equiv 1$知逆元一定存在。

int ans=quick_pow(a,p-2,p); if(ans) printf("%lld\n",quick_pow(a,p-2,p)); else printf("impossible\n"); 

不能这样判断，因为输入数据为2 2，2%2=0逆元应该不存在，但是这里2^0=1，好像没有次幂会为0吧，或许当底数为0的时候…