逆元

1 定义

如果一个线性同余方程 $ax\equiv 1(\mathrm{mod}b)$，则 $x$ 称为 $amodb$ 的逆元，记作 $a^{-1}$。

2 费马小定理：

$x\equiv a^{b-2}(\mathrm{mod}b)$。$p$ 为质数才成立

3 拓展欧几里得：

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;
}
int main() {
    ll x, y;
    Exgcd (a, p, x, y);
    x = (x % p + p) % p;
    printf ("%d\n", x); //x是a在mod p下的逆元
}

4 线性递推求法：

int inv[1000000];
void find_inv(int last,int p)
//求1~last所有数模p意义下的逆元
{
    inv[1]=1;//1的逆元就是1本身
    for(int i=2;i<=last;i++)
        inv[i]=(long long)(p-p/i)*(inv[p%i])%p;
    //注意longlong，否则有可能导致溢出
}

5 线性求任意 n 个数的逆元

上面的方法只能求 $1$ 到 $n$ 的逆元，如果需要求任意给定 $n$ 个数（$1\le a_i<p$）的逆元，就需要下面的方法：

首先计算 $n$ 个数的前缀积，记为 $s_i$，然后使用快速幂或扩展欧几里得法计算 $s_n$ 的逆元，记为 $s{v}_n$。

因为 $s{v}_n$ 是 $n$ 个数的积的逆元，所以当我们把它乘上 $a_n$ 时，就会和 $a_n$ 的逆元抵消，于是就得到了 $a_1$ 到 $a_{n-1}$ 的积逆元，记为 $s{v}_{n-1}$。

同理我们可以依次计算出所有的 $s{v}_i$，于是
$a_i^{-1}$ 就可以用 $s_{i-1}\times s{v}_i$ 求得。

所以我们就在 $O(n+\log p)$ 的时间内计算出了 $n$ 个数的逆元。

s[0] = 1;
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] * a[i] % p;
sv[n] = qpow(s[n], p - 2);
// 当然这里也可以用 exgcd 来求逆元,视个人喜好而定.
for (int i = n; i >= 1; --i) sv[i - 1] = sv[i] * a[i] % p;
for (int i = 1; i <= n; ++i) inv[i] = sv[i] * s[i - 1] % p;

6 一些练习题

6.1 乘法逆元 - OI Wiki 这里有几道题

6.2 ../../ACMExercises/Luogu/B3645 数列前缀和 2 - 洛谷

链接

6.3 B3646 数列前缀和 3 - 洛谷