逆元&欧拉函数_牛客博客

欧拉函数：

　　φ(p)表示小于p的正整数中与p互质的数的个数，称作欧拉函数。

　　求单个数的欧拉函数时可以利用来求

　　其中p_i为p分解出的质因数，k_i表示该质因数的指数

　　代码：

#include<cstdio>
#include<iostream>
using namespace std;
int phi[100];
int Eurl(int x)
{
    int ans=1;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            x/=i;
            ans*=i-1;
        }
        while(x%i==0)
        {
            x/=i;
            ans*=i;
        }
    }
    if(x!=1) ans*=(x-1);
    return ans;
}
int main()
{
    int n=1;
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
         printf("%d\n",Eurl(n));
    }
    return 0;
}

单个欧拉函数

　　还可以求范围内的欧拉函数

　　代码：

#include<cstdio>
#include<iostream>
using namespace std;
int phi[100];
int main()
{
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=1;i<=r;++i)
    phi[i]=i;
    for(int i=2;i<=r+1;++i)
    {
        if(phi[i]==i)
        {
            for(int j=i;j<=r;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);
                
            }
            
        }
    }
    for(int i=l;i<=r;++i)
    {
        printf("%d %d\n",i,phi[i]);
    }
    return 0;
}

范围内欧拉函数

逆元：

　　a*a^-1≡1(mod p)

　　a^-1叫做a在mod p 意义下的逆元。

　　利用欧拉定理可知

　　a^φ(p)≡1(mod p)

　　a*a^φ(p)-1≡1(mod p)

　　所以a在mop p意义下的逆元就是a^φ(p)-1

　　　求单个逆元可以直接这样求

　　一种O(n)求范围内逆元的办法：

　　　　inv[i]=(p-p/i)*inv[p%i]%p

　　证明：

　　　　设t=p/i k=p%i

　　　　易知p≡0(mod p)

　　　　所以t*i+k≡0(mod p)

　　　　t*i≡-k(mod p)

　　　　-t*i≡k(mod p)

　　　　两边都乘以inv[i]和inv[k]

　　　　-t*i*inv[i]*inv[k]≡k*inv[k]*inv[i](mod p)

　　　　-t*inv[k]≡inv[i](mod p)

　　　　所以就得到了

　　　　inv[i]≡(-p/i)*inv[p%i] (mod p)

　　　　所以inv[i]=(p-p/i)*inv[p%i]%p

　　　　用p-p/i是为了避免出现负数

　　代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int inv[110];
 5 int main()
 6 {
 7     int n,p;
 8     scanf("%d%d",&n,&p);
 9     inv[1]=1;
10     for(int i=2;i<=n;++i)
11         inv[i]=inv[p%i]*(p-p/i)%p;
12     for(int i=1;i<=n;++i)
13         printf("%d ",inv[i]);
14     return 0;
15 }

范围内逆元

　　　一种求从1到n间阶乘的逆元的方法

　　　　依据逆元的性质易知

　　　　　　n!*n!^-1≡(n-1)!*(n-1)!^-1≡1(mod p)

　　　　即　n*(n-1)!*n!^-1≡(n-1)!*(n-1)!^-1≡1(mod p)

　　　　然后两边同时乘以(n-1)!^-1得到

　　　　　　n*n!^-1≡(n-1)!^-1(mod p)

　　　　这样就可以倒着递推出范围内阶乘的逆元了

　　　　代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int jsinv[110];
 5 int fai(int k)
 6 {
 7     int ans=1;
 8     for(int i=2;i*i<=k;++i)
 9     {
10         if(k%i==0)
11         {
12             ans*=i-1;
13             k/=i;
14         }
15         while(k%i==0)
16         {
17             ans*=i;
18             k/=i;
19         }
20     }
21     ans*=k;
22     return ans;
23 }
24 int mi(int a,int k,int p)
25 {
26     int ans=1;
27     for(int now=a;k;k>>=1,now=now*now%p)
28         if(k&1) ans=ans*now%p;
29     return ans;
30 }
31 int main()
32 {
33     int n,p;
34     scanf("%d%d",&n,&p);
35     int k=1;
36     for(int i=2;i<=n;++i)
37         k=k*i%p;
38     jsinv[n]=mi(k,fai(p),p);
39     for(int i=n-1;i>=1;--i)
40         jsinv[i]=(jsinv[i+1]*(i+1))%p;
41     for(int i=1;i<=n;++i)
42         printf("%d ",jsinv[i]);
43     return 0;
44 }

范围内阶乘的逆元

逆元&amp;欧拉函数

逆元&欧拉函数