逆元与（扩展）欧拉定理

· · 个人记录

本文主要讲了逆元、（扩展）欧拉定理。

可能更好的阅读体验

快速模幂

P1226 【模板】快速幂||取余运算

假设p为奇数，则b^p=b^{2\lfloor\frac{p}{2}\rfloor+1}=(b^2)^{\lfloor\frac{p}{2}\rfloor}\times b，否则b^p=b^{2\lfloor\frac{p}{2}\rfloor}=(b^2)^{\lfloor\frac{p}{2}\rfloor}

这样可以写一个循环来实现，在p=0时结束循环即可。

#include <bits/stdc++.h>
using namespace std;
int a,b,c,x,y,p,m=1;
int main() {
    for(scanf("%d%d%d",&a,&b,&p),x=a,y=b; b; b>>=1) {
        if(b&1)m=(m*1ll*a)%p;//b为奇数
        a=(a*1ll*a)%p;//将a平方
    }
    printf("%d^%d mod %d=%d\n",x,y,p,m);
    return 0;
}

乘法逆元

对于关于x的同余方程ax\equiv1\pmod p，当且仅当\gcd(a,p)=1时有解，有解时最小正整数解即为a在模p意义下的逆元，记号为a^{-1}。

例如3在模10意义下的逆元即为7。

线性筛逆元

P3811 【模板】乘法逆元

首先1在模p意义下的逆元必定为1

我们考虑n\ge2模p意义下的逆元。

设q=\lfloor\dfrac{p}{n}\rfloor,r=p\%n，则p=nq+r（带余除法的性质）

则nq+r\equiv0\pmod p

把nq移项到右边，两边同时乘上n^{-1}r^{-1}

n^{-1}\equiv-q\times r^{-1}\pmod p

把q=\lfloor\dfrac{p}{n}\rfloor,r=p\%n代入

n^{-1}\equiv(-\lfloor\dfrac{p}{n}\rfloor)(p\%n)^{-1}\pmod p n^{-1}\equiv(p-\lfloor\dfrac{p}{n}\rfloor)(p\%n)^{-1}\pmod p

代码：

#include <bits/stdc++.h>
using namespace std;
int mod,n,inv[20000528];
int main() {
    scanf("%d%d",&n,&mod),inv[1]=1,printf("1\n");
    for(int i=2; i<=n; ++i) {
        inv[i]=(mod-mod/i)*1ll*inv[mod%i]%mod;
        printf("%d\n",inv[i]);
    }
    return 0;
}

欧拉定理

若\gcd(a,p)=1，则a^{\varphi(p)}\equiv1\pmod p

证明：（可不看）

剩余类

剩余类，亦称同余类。

我们把（所有）对模n同余的整数构成的一个集合叫做模n的一个剩余类。

即qn+r（q,r为任意整数）所表示的所有数就是与r模n同余的剩余类

例如\cdots,-11,-5,1,7,13,\cdots就是与1模6同余的剩余类

简化剩余系

简化剩余系也称既约剩余系或缩系

在与 与n互素的整数 模n同余的所有剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模n的一个简化剩余系。

例如模5的一个简化剩余系是1,2,3,4，模30的一个简化剩余系是1,7,11,13,17,19,23,29

根据\varphi(n)的定义，模n的简化剩余系有\varphi(n)个元素。

根据简化同余系的定义，每个模n的简化剩余系的所有元素的乘积模n相等。

证明

设x_1,x_2,\cdots,x_{\varphi(p)}是一个以p为模的缩系。

而且\gcd(a,p)=1，则\gcd(ax_i,p)=1

所以ax_1,ax_2,\cdots,ax_{\varphi(p)}也是一个以p为模的缩系。

所以\prod\limits_{i=1}^{\varphi(p)}ax_i\equiv\prod\limits_{i=1}^{\varphi(p)}x_i\pmod p。

所以a^{\varphi(p)}\equiv 1\pmod p

费马小定理

当p为质数时，a^p\equiv a\pmod p

证明：

当a,p不互质时即p|a，显然成立

当a,p互质时，根据欧拉定理得a^{\varphi(p)}\equiv1\pmod p

而且p为质数时，\varphi(p)=p-1，代入上式后两边同时乘a即可得证。

变式

当\gcd(a,p)=1时，a\times a^{\varphi(p)-1}\equiv1\pmod p

即a模p意义下的逆元为a^{\varphi(p)-1}(当p为质数时，a的逆元为a^{p-2})

快速幂求逆元

直接用欧拉定理的式子即可

#include<bits/stdc++.h>
using namespace std;
int getphi(int n) {
    int tmp=n,ans=n;
    for(int i=2; i*i<=tmp; ++i)
        if(!(tmp%i)) {
            ans-=ans/i;
            while(!(tmp%i))tmp/=i;
        }
    return tmp>1?ans-ans/tmp:ans;
}
int a,b,p,m=1;
int main() {
    for(scanf("%d%d",&a,&p),b=getphi(p)-1; b; b>>=1) {
        if(b&1)m=(m*1ll*a)%p;
        a=(a*1ll*a)%p;
    }
    printf("%d\n",m);
    return 0;
}

扩展欧几里得求逆元

扩展欧几里得相关见同余基础数论详解

P1082 [NOIP2012 提高组] 同余方程

这题其实就是求a模b意义下的逆元。

有解说明\gcd(a,b)|1，那么\gcd(a,b)=1，直接用扩展欧几里得解同余方程即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,mod,x,y,d;
void exgcd(ll a,ll b,ll&x,ll&y,ll&gcd) {
    if (!b) gcd=a,x=1,y=0;
    else exgcd(b,a%b,y,x,gcd),y-=a/b*x;
}
int main() {
    scanf("%lld%lld",&a,&mod);
    exgcd(a,mod,x,y,d);
    printf("%lld\n",(x%mod+mod)%mod);//记得取模
    return 0;
}

求多个数的逆元

P5431 【模板】乘法逆元2

我们这题要求a_1,a_2,\cdots,a_n模p意义下的逆元，我们可以试着用O(n+\log p)求

设s_i=\prod\limits_{i=1}^ia_i\mod p，可以O(n)预处理出s_i

再设b_{i+1}=\prod\limits_{i=1}^i(a_i)^{-1}\pmod p，可得(a_i)^{-1}\equiv b_{i+1}\times s_{i-1}\pmod p

接下来就是要考虑如何处理b_{i+1}：

预处理s_i后，b_{n+1}=s_n^{-1}\pmod p，是O(\log p)

之后i从n到1的循环，算出a_i^{-1}\equiv b_{i+1}\times s_{i-1}\pmod p，同时算出b_i\equiv b_{i+1}\times a_i\pmod p即可。

总复杂度O(n+\log p)

#include <bits/stdc++.h>
using namespace std;
inline int read() {
    int x=0,c=getchar();
    for(; c<=47||c>=58; c=getchar());
    for(; c>=48&&c<=57; c=getchar())x=(x<<3)+(x<<1)+(c&15);
    return x;
}
const int MAXN=1<<23;
int n,mod,k,b[MAXN],s[MAXN],a[MAXN],inv[MAXN],ans;
int fastpow(int a,int k) {
    int base=1;
    for(; k; a=((0ll+a)*a)%mod,k>>=1)
        if(k&1)
            base=((0ll+base)*a)%mod;
    return base;
}
int main() {
    s[0]=1;
    n=read(),mod=read(),k=read();
    for(int i=1; i<=n; ++i) {
        a[i]=read();
        s[i]=s[i-1]*1ll*a[i]%mod;//预处理si
    }
    b[n+1]=fastpow(s[n],mod-2);
    for(int i=n; i>=1; --i) {
        inv[i]=b[i+1]*1ll*s[i-1]%mod;//逆元
        b[i]=b[i+1]*1ll*a[i]%mod;//bi
    }
    int tmp=k;
    for(int i=1; i<=n; i++) {
        ans=(ans+inv[i]*1ll*tmp)%mod;//计算答案
        tmp=(tmp*1ll*k)%mod;
    }
    printf("%d\n",ans);
    return 0;
}

有理数取余

P2613 【模板】有理数取余

\dfrac{a}{b}\equiv a\times b^{-1}\pmod p

直接用上面说的求逆元即可。

#include<bits/stdc++.h>
using namespace std;
const int mod=19260817;
inline int read() {
    int x=0,c=getchar();
    for(; c<=47||c>=58; c=getchar());
    for(; c>=48&&c<=57; c=getchar())x=((x<<3)+(x<<1)+(c&15))%mod;
    return x;
}
int fastpow(int a,int k) {
    int base=1;
    while(k) {
        if(k&1) base=base*1ll*a%mod;
        a=a*1ll*a%mod;
        k>>=1;
    }
    return base;
}
int a,b;
int main() {
    a=read(),b=read();
    printf("%d\n",a*1ll*fastpow(b,mod-2)%mod);
    return 0;
}

扩展欧拉定理

当b\ge\varphi(m)时，a^{b}\equiv a^{(b\mod \varphi(m))+\varphi(m)}\pmod m

P5091 【模板】扩展欧拉定理

证明：

首先m=1时，\varphi(m)=1，结论成立。

任取一个质数p，m就可以写成p^r\times s，其中r\ge0,\gcd(p,s)=1。

则\varphi(p^r)\times \varphi(s)=\varphi(m)（\varphi是积性函数）

由欧拉定理得p^{\varphi(s)}\equiv 1\pmod s，则p^{\varphi(m)}\equiv1\pmod s

可以设p^{\varphi(m)}=ts+1，将式子两边乘上p^r：

p^{\varphi(m)+r}=tm+p^r$，即$p^{\varphi(m)+r}\equiv p^r\pmod m

当b\ge r时，p^{b}\equiv p^{b-r}p^r\equiv p^{b-r}p^{\varphi(m)+r}\equiv p^{b+\varphi(m)}\pmod m

且r\leq \varphi(p^r)\leq \varphi(m)，所以在b\geq\varphi(m)时，上式成立。

改写一下上面的结论：

当b\ge2\varphi(m)即b-\varphi(m)\ge\varphi(m)时，p^{b}\equiv p^{b-\varphi(m)}\pmod m

也就是p^{b}\equiv p^{(b\mod \varphi(m))+\varphi(m)}\pmod m

把a分解质因数后得到的所有质数都会满足上式，把它们乘起来就是a也满足。

模板题代码：

#include <bits/stdc++.h>
using namespace std;
int m,a,b,phi;
int getphi(int n) {//求phi
    int tmp=n,ans=n;
    for(int i=2; i*i<=tmp; ++i)
        if(!(tmp%i)) {
            ans-=ans/i;
            while(!(tmp%i))tmp/=i;
        }
    return tmp>1?ans-ans/tmp:ans;
}
void read(int&b) {
    bool gt=0;
    char c=getchar();
    for(; c<'0'||c>'9'; c=getchar());
    for(; c>='0'&&c<='9'; c=getchar()) {
        b=(b<<3)+(b<<1)+(c^48);
        gt|=b>=phi;//判断b是否大于phi
        b%=phi;
    }
    if(gt)b+=phi;//不大于就不能加
}
int quickpow(int a,int b,int p) {//快速幂
    int m=1;
    while(b) {
        if(b&1)m=(m*1ll*a)%p;
        a=(a*1ll*a)%p;
        b>>=1;
    }
    return m;
}
int main() {
    scanf("%d%d",&a,&m),phi=getphi(m),read(b);
    printf("%d\n",quickpow(a,b,m));
    return 0;
}

一道题

P4139 上帝与集合的正确用法

这个2^{2^{2\cdots}}明显大于\varphi(p)，根据扩展欧拉定理

2^{2^{2\cdots}}\equiv 2^{2^{2^{2\cdots}}\mod \varphi(p)+\varphi(p)}\pmod p

这样就可以递归，直到p=1,2时返回0即可。

#include<bits/stdc++.h>
using namespace std;
int fastpow(int a,int k,const int mod) {
    int base=1;
    while(k) {
        if(k&1)base=base*1ll*a%mod;
        a=a*1ll*a%mod;
        k>>=1;
    }
    return base;
}
int phi(int n) {
    int tmp=n;
    for(int i=2; i*i<=n; ++i)
        if(!(n%i))
            for(tmp-=tmp/i; !(n%i); n/=i);
    return n>1?tmp-tmp/n:tmp;
}
int solve(int mod) {
    int t=phi(mod);
    return mod==1||mod==2?0:fastpow(2,solve(t)+t,mod);//递归
}
int n,t;
int main() {
    scanf("%d",&t);
    while(t--) {
        scanf("%d",&n);
        printf("%d\n",solve(n));
    }
    return 0;
}