逆元

1 定义

如果一个线性同余方程 \(ax \equiv 1 \pmod b\)，则 \(x\) 称为 \(a \bmod b\) 的逆元，记作 \(a^{-1}\)。 ## 2 费马小定理： \(x \equiv a^{b-2} \pmod 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\) 的逆元，记为 \(sv_n\)。

因为 \(sv_n\) 是 \(n\) 个数的积的逆元，所以当我们把它乘上 \(a_n\) 时，就会和 \(a_n\) 的逆元抵消，于是就得到了 \(a_1\) 到 \(a_{n-1}\) 的积逆元，记为 \(sv_{n-1}\)。

同理我们可以依次计算出所有的 \(sv_i\)，于是 \(a_i^{-1}\) 就可以用 \(s_{i-1} \times sv_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 [[B3645 数列前缀和 2 - 洛谷]]

链接 ### 6.3 B3646 数列前缀和 3 - 洛谷