算法竞赛中常用的数论知识
2025-08-27 14:24:25 #math

1.乘法逆元

(注：算法1、算法3、算法4只要求$\forall a_i,(a_i,p)=1$,算法2要求p是素数)

1.扩展欧几里得算法

朴素欧几里得算法：

1
2
3
4
5
6
7
8
int gcd(int a, int b) {
    while (b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

利用朴素欧几里得算法，我们可以求出$gcd(a,b)$,根据裴蜀定理，$ax+by=gcd(a,b)$，在一些情况下我们需要求解x,y，为此，我们可以使用扩展欧几里得算法。
$ax+by=gcd(a,b)=gcd(b,a%b)$,那么$bx_1+(a%b)y_1=bx_1+(a-[a/b]*b)y_1=ay_1+b(x_1-[a/b]*y_1)=g$,所以$x=x_1,y=y_1-[a/b]*x_1$.
由此我们可以递归求解，退出条件和朴素欧几里得算法一致，为$b=0$时返回$a,1,0$.

1
2
3
4
5
using ll = long long;
void exgcd(ll a,ll b,ll&x,ll&y){
    if(!b)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}

这样得到一组特解，通解为$x=x_0+\frac{b}{d}t,y=y_0-\frac{a}{d}t$，其中$d=gcd(a,b),t$为任意整数。
求最小非负整数解：$x=((x\ modb)+b)\ modb,y=((y\ moda)+a)\ moda$。
那么，当$(a,b)=1时$，x即为a mod b的逆元

2.费马小定理+快速幂

当$p$为质数时，$a^{p-1}\equiv1\ mod\ p$，所以$a^{p-2}\equiv a^{-1}\ mod\ p$，我们可以利用快速幂求解$a^{-1}\ mod\ p$。

1
2
3
4
5
6
7
8
9
10
11
using ll = long long;
ll qpow(ll a,ll b,ll p){
    ll res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}
//qpow(a,p-2,p)即为所求

3.线性算法

base: $1^{-1}\equiv1\ mod\ p$
递推:对于$i,p=ki+r$(带余除法),$ki+r\equiv0\ mod\ p,i^{-1}\equiv -kr^{-1}\ mod\ p\equiv -[p/i](p%i)^{-1}\ mod\ p$

1
2
3
4
inv[1]=p;
for(int i=2;i<=n;i++){
    inv[i]=(p-p/i)*inv[p%i]%p;
}

4. 线性阶乘逆元

递推关系：
$$
\text{inv}[i+1] = \frac{1}{(i+1)!}
$$
将等式两边同乘 $(i+1)$：
$$
\text{inv}[i+1] \cdot (i+1) = \frac{1}{i!} = \text{inv}[i]
$$

因此，我们只要先求出 $n!$ 的逆元，然后利用递推关系，就可以依次推出 $1!, 2!, \dots, n!$ 的所有逆元。

递推式为：
$$
\text{inv}[i+1] \cdot (i+1) = \text{inv}[i]
$$

于是我们就可以得到 $\forall i \frac{1}{i!}$ 的取值。

接下来，我们注意到：
$$
\frac{1}{i} \equiv \frac{1}{i!} \times (i-1)! \pmod{p}
$$

也就是说，我们可以用阶乘逆元来快速得到所有整数$1,2,\dots,n$ 的逆元。

C++ Code (solution3和4可以AC) 

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//solution1
#include<iostream>
using namespace std;
using ll = long long;
inline void exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;//note:不要写成x*a/b!!!!
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        ll x,y;
        exgcd(i,p,x,y);
        x=((x%p)+p)%p;//转化为正数
        cout<<x<<'\n';
    }
}

//solution2
#include<iostream>
using namespace std;
using ll=long long;
int qpow(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1)ans=(ll)ans*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    int n,p;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cout<<qpow(i,p-2,p)<<'\n';
    }
}

//solution3
#include<iostream>
using namespace std;
const int MAX=3e6+5;
int inv[MAX];
int main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    int n,p;
    cin>>n>>p;
    inv[1]=1;
    cout<<1<<'\n';
    for(int i=2;i<=n;++i){
        inv[i]=((p-p/i)*(long long)inv[p%i])%p;//小心中间乘法越界
        cout<<inv[i]<<'\n';
    }
}

//solution4
#include<iostream>
using namespace std;
using ll = long long;
inline void exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;//note:不要写成x*a/b!!!!
}
const int MAX=3e6+5;
int invfac[MAX];
int fac[MAX];
int main(){
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    int n,p;
    cin>>n>>p;
    fac[1]=1;
    for(int i=2;i<=n+1;i++){
        fac[i]=(ll)fac[i-1]*i%p;
    }
    ll x,y;
    exgcd(fac[n+1],p,x,y);
    invfac[n+1]=((x%p)+p)%p;//注意这里
    for(int i=n;i>=1;i--)invfac[i]=(ll)invfac[i+1]*(i+1)%p;
    cout<<1<<'\n';
    for(int i=1;i<=n-1;i++){
        cout<<(ll)fac[i]*invfac[i+1]%p<<'\n';
    }
}

5. 多个数逆元的离线做法

借用线性阶乘逆元的思路即可

Prev
Next