跳转至

取模意义下的逆元

如果一个线性同余方程 \(ax \equiv 1 \pmod p\) 成立,则称 \(x\)\(a\) 在模 \(p\) 意义下的逆元,记作 \(x=a^{-1}\)

注意溢出

逆元相关的算法涉及大量的指数和乘法运算,一定要开 long long

exgcd 求逆元

逆元的定义是一个线性同余方程,我们可以将它转化为一个二元一次不定方程:

\[ ax-py=1 \]

这种方程可以使用扩展欧几里得算法求出一组解 \((x,y)\),其中的 \(x\) 就是 \(a\) 的一个逆元。

注意,扩欧的 \(O(\log a)\) 时间复杂度是其理论上界。经实测,其具有非常小的常数。

逆元存在定理

\(a\) 在模 \(p\) 意义下(\(1\le a<p\))存在乘法逆元的充要条件是 \(a\)\(p\) 互质。

费马小定理求逆元

引理

\(a\)\(p\) 互质(\(1\le a<p\))时,\(a,2a,3a,\cdots (p-1)a\)\(p\) 的结果覆盖 \([1,p-1]\) 的所有整数。

证明

假设存在 \(1\le x<y<p\) 满足 \(xa\equiv ya\pmod p\),那么有 \(p\mid (y-x)a\)。由于 \(a\)\(p\) 互质,因此 \(p\mid y-x\),显然与 \(1\le x<y<p\) 矛盾。证毕。

费马小定理:若 \(p\) 为质数,\(1\le a<p\),则

\[ a^{p-1} \equiv 1 \pmod p \]
证明

由引理可得,

\[ (a)(2a)(3a)\cdots\big((p-1)a\big)\equiv (p-1)!\pmod p \]

变形得

\[ (p-1)!a^{p-1}\equiv (p-1)!\pmod p \]

当且仅当 \(p\) 是质数,\((p-1)!\) 的逆元存在。此时有

\[ a^{p-1}\equiv 1\pmod p \]

由此我们可以得到:

\[ a^{p-2}\times a \equiv 1 \pmod p \]

根据定义,\(a^{p-2}\) 正是 \(a\) 的一个逆元。我们可以使用快速幂以 \(O(\log_2{p})\) 的时间复杂度求出。

线性求逆元

例题

给定一个正整数 \(n\) 和一个质数 \(p\)\(n<p\)),输出所有 \(i\in[1,n]\) 的逆元 \(i^{-1}\)

\(n\le 3\times 10^6\)

我们必须在 \(O(n)\) 的时间复杂度内求出总共 \(n\) 个数的逆元。对于数字 \(i\),假如我们已经求出了所有 \(j<i\) 的逆元 \(j^{-1}\)。将质数 \(p\)\(i\) 取模:

\[ p=\lfloor\frac{p}{i}\rfloor\times i+r \]

其中 \(r<i\);由此得到:

\[ \begin{align*} \lfloor\frac{p}{i}\rfloor\times i+r\equiv 0 \pmod p\\ \lfloor\frac{p}{i}\rfloor\times i\equiv -r \pmod p \end{align*} \]

我们将方程两边同时乘以 \(i^{-1}r^{-1}\)

\[ i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor\times r^{-1} \pmod p \]

就得到了 \(i\) 的逆元。

代码

int n, p;
int inv[N];

int main() {

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

    return 0;
}

通过这种方法,我们做到可以 \(O(n)\) 预处理,\(O(1)\) 求出组合数 \(\binom{a}{b}\)\(a,b\le n\)

质因子分离法 / 模数不是质数

这种方法能实现对一个数字进行累乘累除模数 \(p\) 不是质数的情况。

我们先对 \(p\) 进行质因子分解;每次操作都将操作数 \(x\) 中所有 \(p\) 的质因子单独分离出来,单独处理;剩下的数一定和 \(p\) 互质,可以使用 exgcd 求出逆元。

代码
int notPri[P], pri[P], pcnt;

// 筛出 [1,n] 区间内的所有质数
void prime() {
    for(int i = 2; i <= p; i++) {
        if(!notPri[i]) pri[++pcnt] = i;
        for(int j = 1; j <= pcnt; j++) {
            if(i * pri[j] > p) break;
            notPri[i * pri[j]] = 1;
            if(i % pri[j] == 0) break;
        }
    }
}

// 快速幂
int qpow(int a, int b) {
    int res = 1;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

// 扩欧求逆元
void exgcd(const int &a, const int &b, int &x, int &y, int &d) {
    if(b == 0) {
        x = 1, y = 0;
        d = a;
        return;
    }
    exgcd(b, a % b, y, x, d);
    y -= a / b * x;
}

// 互质逆元
int inv(int a) {
    int x, y, d;
    exgcd(a, p, x, y, d);
    if(d != 1) throw "gcd(a, p) != 1";
    x = (x % p + p) % p;
    return x;
}

// pp[i] 储存 p 的质因数分解结果
// cnt[i] 表示质因子 pri[pp[i]] 的幂次
// num 表示跟 p 互质的那部分是多少
int pp[50], ppcnt;
int cnt[50], num = 1;

// 乘法
void mul(int x) {
    for(int i = 1; i <= ppcnt; i++) {
        while(x % pri[pp[i]] == 0) {
            x /= pri[pp[i]];
            cnt[i]++;
        }
    }
    num = num * x % p;
}

// 除法
void div(int x) {
    for(int i = 1; i <= ppcnt; i++) {
        while(x % pri[pp[i]] == 0) {
            x /= pri[pp[i]];
            cnt[i]--;
        }
    }
    num = num * inv(x) % p;
}

// 返回结果
int calc() {
    int res = 1;
    for(int i = 1; i <= ppcnt; i++) {
        res = res * qpow(pri[pp[i]], cnt[i]) % p;
    }
    res = res * num % p;
    return res;
}