同余，逆元与exgcd

一、同余

显然在OI中有大量的取模运算，我们要使得到的余数不变，故引入同余
若 \(a \equiv b \pmod{m}\)，\(c \equiv d \pmod{m}\)，则有：

  • \(a + c \equiv b + d \pmod{m}\)
  • \(a - c \equiv b - d \pmod{m}\)
  • \(a \cdot c \equiv b \cdot d \pmod{m}\)
    这些性质让我们可以放心地边算边取模，如：
// 计算 (a*b + c) % mod
int ans = (1LL * a * b % mod + c) % mod;

我们需要注意，除法并没有如上性质，故将会引入逆元

注意：C++中，我们对一个负数去模会得到负数，故有次解决方法

int mod(int x, int m) {return (x % m + m) % m;
}

二、逆元与exgcd

1.逆元

我们在上文说了除法没有同余的性质，所以逆元就是解决方案

在模 \(m\) 意义下，若整数 \(a\) 满足 \(\gcd(a,m)=1\)，那么存在一个整数 \(x\)，使得：

\[a x \equiv 1 \pmod m \]

这个 \(x\) 就叫做 \(a\) 在模 \(m\) 下的乘法逆元，记作 \(a^{-1}\) 或 \(\text{inv}(a)\)。
而我们要注意其存在与否：\(a\) 在模 \(m\) 下有逆元，当且仅当 \(\gcd(a,m)=1\)。
特别地，当 \(m\) 是质数时，只要 \(a\) 不是 \(m\) 的倍数，逆元就存在。

有了逆元，我们可以做到除法运算，如下：
比如想算 \(\dfrac{b}{a} \bmod m\)，不能直接除。正确做法是：

\[\frac{b}{a} \equiv b \cdot a^{-1} \pmod m \]

求出 \(a\) 的逆元，把除法变成乘法，这一点有点类比于小学学除法是转换成倒数算？

2.exgcd

（1）.🍭

那么如何求逆元，我们将引入exgcd

裴蜀定理：对任意不全为 0 的整数 𝑎, 𝑏，存在整数 𝑥, 𝑦，使得 𝑎𝑥 + 𝑏𝑦 = gcd(𝑎, 𝑏)。（我也不知道为什么，反正老师说背下来，当然应该是我菜）

（2）推导

exgcd的推导摘自课件：

推导如下。设
𝑎=𝑞𝑏+𝑟, 𝑟=𝑎mod 𝑏.

递归会先求出𝑏,𝑟的答案。

若𝑏𝑢+𝑟𝑣=gcd (𝑏,𝑟),代入𝑟=𝑎−𝑞𝑏：
𝑏𝑢+(𝑎−𝑞𝑏)𝑣=𝑎𝑣+𝑏(𝑢−𝑞𝑣)=gcd (𝑎,𝑏).

因此𝑎,𝑏的系数应分别取
𝑥=𝑣, 𝑦=𝑢−𝑞𝑣.

这就是递归调用把两个引用参数交换的原因：递归返回时，𝑢,𝑣分别存放在当前
的𝑦,𝑥中；执行𝑦←𝑦−⌊𝑎𝑏⌋𝑥后，恰好得到新的𝑦=𝑢−𝑞𝑣。
时间复杂度为𝑂(log min(𝑎,𝑏))（同普通gcd）

我们给出模版：

// 返回 gcd(a,b)，并求出 x,y 满足 ax + by = gcd(a,b)
int exgcd(int a, int b, int &x, int &y) {if (b == 0) {x = 1, y = 0;return a;}int d = exgcd(b, a % b, y, x); // 注意这里 x,y 交换了位置y -= a / b * x;                // 对应 y = x' - a/b * y'return d;
}

至于只求出了一个解，实际中我们有特殊情况，下面我一会就去学（）

我们先说如何求逆元，根据我对课件的观察，只需要取模使其在[0,m-1], return (x % mod + mod) % mod;

（3）通解

设 \(d = \gcd(a,b)\)，且 \(d \mid c\)，则方程 \(a x + b y = c\) 的一组特解为：

\[x_1 = x_0 \cdot \frac{c}{d}, \quad y_1 = y_0 \cdot \frac{c}{d} \]

所有整数解表示为：

\[\boxed{ x = x_1 + k \cdot \frac{b}{d}, \quad y = y_1 - k \cdot \frac{a}{d} \qquad (k \in \mathbb{Z}) } \]

其中 \(\frac{b}{d}\) 和 \(\frac{a}{d}\) 都是整数。

3.求逆元的其他一些方式

（1）费马小定理

若 \(p\) 是质数，且整数 \(a\) 满足 \(p \nmid a\)（即 \(\gcd(a,p)=1\)），则有：

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

由此可变形得到逆元公式：

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

适用条件：模数 \(p\) 必须为质数，且 \(a\) 不是 \(p\) 的倍数。

解释：
若 \(p\) 是质数，且整数 \(a\) 满足 \(p \nmid a\)（即 \(\gcd(a,p)=1\)），则有：

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

由此可变形得到逆元公式：

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

ll powM(ll a,int t=mod-2)
{ll ret=1;while(t){if (t&1)ret=ret*a%mod;a=a*a%mod;t>>=1;}return ret;
}

ll qpow(ll a, ll e, ll mod) {ll r = 1;for (; e; e >>= 1, a = (__int128)a * a % mod)if (e & 1) r = (__int128)r * a % mod;return r;
}
ll inv_prime(ll a, ll p) {return qpow(a, p - 2, p);
}

（2）线性递推

我是傻子我不会推，但是好像背板子就行了（）

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

复杂度为 𝑂(𝑛)，实现时必须保证 𝑛 < p

还有一种可以O(1)求出组合，但鄙人学识浅薄，背板子了

fac [0] = 1;
for (int i = 1; i <= n; ++i) fac [i] = fac [i - 1] * i % p;
ifac [n] = qpow (fac[n], p - 2 , p);
for (int i = n; i >= 1; --i) ifac [i - 1] = ifac [i] * i % p;
for (int i = 1; i <= n; ++i) inv [i] = fac [i - 1] * ifac [i] % p;