P3811 【模板】模意义下的乘法逆元 题解

【模板】模意义下的乘法逆元

题目背景

这是一道模板题

题目描述

给定 n , p n,p n,p 求 1 ∼ n 1\sim n 1∼n 中所有整数在模 p p p 意义下的乘法逆元。

这里 a a a 模 p p p 的乘法逆元定义为 a x ≡ 1 ( m o d p ) ax\equiv1\pmod p ax≡1(modp) 的解。

输入格式

一行两个正整数 n , p n,p n,p。

输出格式

输出 n n n 行，第 i i i 行表示 i i i 在模 p p p 下的乘法逆元。

样例 #1

样例输入 #1

10 13

样例输出 #1

1
7
9
10
8
11
2
5
3
4

提示

$ 1 \leq n \leq 3 \times 10 ^ 6 ， ， ，n < p < 20000528 $。

输入保证 $ p $ 为质数。

乘法逆元小结

乘法逆元，一般用于求 $$\frac{a}{b} \pmod p$$ 的值（ppp 通常为质数），是解决模意义下分数数值的必要手段。

逆元定义

若a∗x≡1(modb)a*x\equiv1 \pmod {b}a∗x≡1(modb)，且aaa与bbb互质，那么我们就能定义: xxx 为 aaa 的逆元，记为a−1a^{-1}a−1，所以我们也可以称 xxx 为 aaa 在  mod b\bmod bmodb 意义下的倒数，

所以对于 ab(modp)\displaystyle\frac{a}{b} \pmod {p}ba​(modp) ，我们就可以求出 bbb 在  mod p\bmod {p}modp 下的逆元，然后乘上 aaa ，再  mod p\bmod {p}modp，就是这个分数的值了。

求解逆元的方式

拓展欧几里得

这个方法十分容易理解，而且对于单个查找效率似乎也还不错，比后面要介绍的大部分方法都要快(尤其对于  mod p\bmod {p}modp 比较大的时候)。

这个就是利用拓欧求解 线性同余方程 a∗x≡c(modb)a*x \equiv c \pmod {b}a∗x≡c(modb) 的c=1c=1c=1的情况。我们就可以转化为解 a∗x+b∗y=1a*x + b*y = 1a∗x+b∗y=1 这个方程。

求解这个方程的解。不会拓欧可以点这里~

而且这个做法还有个好处在于，当 a⊥pa \bot pa⊥p （互质），但 ppp 不是质数的时候也可以使用。

代码比较简单：

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下的逆元
}

快速幂

这个做法要利用 费马小定理

若ppp为素数，aaa为正整数，且aaa、ppp互质。 则有ap−1≡1( mod p)a^{p-1} \equiv 1 (\bmod {p})ap−1≡1(modp)。

这个我们就可以发现它这个式子右边刚好为 111 。

所以我们就可以放入原式，就可以得到：

a∗x≡1(modp)a*x\equiv 1 \pmod p a∗x≡1(modp)

a∗x≡ap−1(modp)a*x\equiv a^{p-1} \pmod p a∗x≡ap−1(modp)

x≡ap−2(modp)x \equiv a^{p-2} \pmod p x≡ap−2(modp)

所以我们可以用快速幂来算出 ap−2(modp)a^{p-2} \pmod pap−2(modp)的值，这个数就是它的逆元了

代码也很简单：

ll fpm(ll x, ll power, ll mod) {
    x %= mod;
    ll ans = 1;
    for (; power; power >>= 1, (x *= x) %= mod)
    	if(power & 1) (ans *= x) %= mod;
    return ans;
}
int main() {
	ll x = fpm(a, p - 2, p); //x为a在mod p意义下的逆元
}

线性算法

用于求一连串数字对于一个 mod p\bmod pmodp的逆元。洛谷P3811

只能用这种方法，别的算法都比这些要求一串要慢。

首先我们有一个,1−1≡1(modp)1^{-1}\equiv 1 \pmod p1−1≡1(modp)

然后设 p=k∗i+r,(1<r<i<p)p=k*i+r,(1<r<i<p)p=k∗i+r,(1<r<i<p) 也就是 kkk 是 p/ip / ip/i 的商，rrr 是余数 。

再将这个式子放到(modp)\pmod p(modp)意义下就会得到：

k∗i+r≡0(modp)k*i+r \equiv 0 \pmod p k∗i+r≡0(modp)

然后乘上i−1i^{-1}i−1,r−1r^{-1}r−1就可以得到:

k∗r−1+i−1≡0(modp)k*r^{-1}+i^{-1}\equiv 0 \pmod p k∗r−1+i−1≡0(modp)

i−1≡−k∗r−1(modp)i^{-1}\equiv -k*r^{-1} \pmod p i−1≡−k∗r−1(modp)

i−1≡−⌊pi⌋∗(p mod i)−1(modp)i^{-1}\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} \pmod p i−1≡−⌊ip​⌋∗(pmodi)−1(modp)

于是，我们就可以从前面推出当前的逆元了。

代码也很短：

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

阶乘逆元 O(n)O(n)O(n) 求

因为有如下一个递推关系。

inv[i+1]=1(i+1)!\displaystyle inv[i+1]=\frac{1}{(i+1)!}inv[i+1]=(i+1)!1​

inv[i+1]∗(i+1)=1i!=inv[i]\displaystyle inv[i+1]*(i+1)=\frac{1}{i!}=inv[i]inv[i+1]∗(i+1)=i!1​=inv[i]

所以我们可以求出n!n!n!的逆元，然后逆推，就可以求出1...n!1...n!1...n!所有的逆元了。

递推式为

inv[i+1]∗(i+1)=inv[i]inv[i+1]*(i+1)=inv[i]inv[i+1]∗(i+1)=inv[i]

所以我们可以求出 ∀i,i!,1i!\displaystyle \forall i, i!,\frac{1}{i!}∀i,i!,i!1​ 的取值了。

然后这个也可以导出 1i(modp)\displaystyle \frac{1}{i} \pmod pi1​(modp) 的取值，也就是

1i!×(i−1)!=1i(modp)\displaystyle \frac{1}{i!} \times (i - 1)! = \frac{1}{i} \pmod p i!1​×(i−1)!=i1​(modp)