wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

[[ item.c ]]

同余与模的一些问题

## 模 m 等价类
设$$a, b, m$$是三个整数，其中$$m > 0$$，如果满足$$a \bmod m = b \bmod m$$，那么认为$$a, b$$在模$$m$$意义下，等价
记为$$a \equiv b (\bmod m)$$

**等价类**
记集合$$\bold{i} = \\{x \mid x \equiv i (\bmod m)\\}$$，这是关于$$m$$的
这些集合实际上只有$$\\{\bold{0}, \bold{1}, \cdots, \bold{m-1}\\}$$

**等价类上的运算**
在$$\mathbb{Z}\_m = \\{\bold{0}, \bold{1}, \cdots, \bold{m - 1}\\}$$上定义两种运算$$+, \times$$
其中，$$\bold{a} + \bold{b} = \bold{c}$$当且仅当$$\forall a \in \bold{a}, b \in \bold{b}$$，有$$a+b \in \bold{c}$$
$$\bold{a} \times \bold{b} = \bold{c}$$，当且仅当$$\forall a \in \bold{a}, b \in \bold{b}$$，有$$a\times b \in \bold{c}$$

**逆元**
如果$$\bold{a, b} \in \mathbb{Z}\_m$$，满足$$\bold{ab} = \bold{1}$$，那么$$\bold{b}$$是$$\bold{a}$$的逆元
记为$$\bold{a}^{-1}$$

### 求逆元
判定在$$\mathbb{Z}\_m$$里，$$\bold{a}$$是否有逆元，如果有，怎么求$$\bold{a}^{-1}$$

> 可以用 exgcd 来求逆元

如果$$ab \equiv 1 (\bmod m)$$，那么$$ab = km + 1$$，求这个不定方程
```math
ab - mk = 1
```
将$$(b, k)$$设为未知的，那么有逆元的充要条件，是$$gcd(a, m) = 1$$

> 由此可以得到充要条件
$$\bold{a}$$在$$\mathbb{Z}\_m$$内有逆元，当且仅当$$(a, m) = 1$$
如果$$m$$是质数，则任意的$$0 < a < m$$，$$\bold{a} \in \mathbb{Z}\_m$$有逆

那么$$\bmod m$$等价类中，有几个数有逆元呢？答案是$$\phi(m)$$

### 欧拉定理
如果$$(a, m) = 1$$，那么$$a^{\phi(m)} \equiv 1 (\bmod m)$$

> 如果有欧拉定理，我们可以很方便求出逆元

因为$$a^{\phi(m) - 1} \cdot a \equiv 1(\bmod m)$$，那么$$a$$的逆元就是$$a^{\phi(m) - 1}$$

> 证明，构造等价类

定义$$S = \\{ i\_1, i\_2, \cdots,  i\_{\phi(m)}\\}$$，为$$[1, 2, \cdots, m]$$中和$$m$$互质的所有的数

构造一个$$f: S \to S$$的映射，定义$$f(i) = (ai) \bmod m$$
注意到$$(m, ai) = 1 = (m, ai \bmod m)$$，那么所有的$$\\{ai\\}$$是不是也能恰好构成集合$$S$$呢？
也就是说，我们要尝试证明$$f$$是$$S \to S$$的**一一映射**

对于$$i \neq j$$，$$f(i) \neq f(j)$$，即$$ai \not \equiv aj (\bmod m)$$
可以用反证法

假设$$ai \equiv aj(\bmod m)$$，因为$$(a, m) = 1$$，所以$$a^{-1} \cdot ai \equiv a^{-1} \cdot aj (\bmod m)$$
从而$$i \equiv j (\bmod m)$$，而前提条件假设$$i \neq j$$，矛盾

那么这样的话，我们就有
```math
i_1 i_2 \cdots i_{\phi(m)} \equiv ai_1 ai_2 \cdots ai_{\phi(m)} (\bmod m)
```
而$$\\{i\_{1}, i\_{2}, \cdots, i\_{\phi(m)} \\}$$都是和$$m$$互质的，因此有逆元
从而有$$a^{\phi(m)} \equiv 1 (\bmod m)$$

### 费马小定理
这是欧拉定理的推论，设$$p$$是质数，如果$$p \nmid a$$，那么$$a^{p-1} \equiv 1 (\bmod p)$$
从而$$a$$的逆元就是$$a^{p-2}$$

### 逆元求法
设$$m$$是正整数，$$\bold{a} \in \mathbb{Z}\_m, (a, m) = 1$$，逆元$$\bold{a}^{-1} = \bold{a}^{\phi(m) - 1}$$

设$$p$$是质数，$$\bold{a} \in \mathbb{Z}\_{p}, 0 < a < p$$，逆元$$\bold{a}^{-1} = \bold{a}^{p-2}$$

## 一些问题
### 模版题
**[模版题](https://ac.nowcoder.com/acm/contest/21289/A)**
求关于$$x$$的同余方程$$ax \equiv 1 (\bmod b)$$的最小正整数解

**算法分析**
实际上是求解不定方程，$$ax + bk = 1$$，可以用扩展欧几里得算法，求出合法的特解$$(x_0, k_0)$$
那么对于$$ax + bk = 1$$，不难发现$$(x_0 + lb, k_0 - la)$$也是一组合法的解

找到最小的正整数$$x_0 + lb$$即可，可以用扩展欧几里得求出合法的解之后，考虑`res = safeMod(x, b)`，就是答案

如果$$gcd(a, b) > 1$$，无解

更简单的方法是，实际上这是要我们求模$$b$$意义下的逆元（取最小正整数），答案就是$$x = (a^{\phi(m) - 1}) \bmod b$$

```bash
void solve(int cas) {
    i64 a, b;
    cin >> a >> b;
 
    auto g = std::gcd(a, b);
    if (g != 1) {
        cout << "-1\n";
        return;
    }
 
    auto [g2, x, k] = exgcd(a, b);
    auto res = safeMod(x, b);
    cout << res << "\n";
}
```

## 逆元表
对于很大的质数$$P$$，一般来说，$$P > i$$，我们可以构造逆元表
```math
\displaystyle
p = \lfloor \dfrac{p}{i} \rfloor \cdot i + (p \bmod i) \\
\lfloor \dfrac{p}{i} \rfloor \equiv (-p \bmod i) \quad  (\bmod p)\\

\left( (p \bmod i)^{-1} \cdot  -\lfloor \dfrac{p}{i} \rfloor  \right) \cdot i \equiv 1 \quad (\bmod p)
```
从而有递推
```math
inv(i) = (p -  \lfloor \dfrac{p}{i} \rfloor ) \cdot inv(p \bmod i)
```

## 逆元的应用
**[Alternating Sum](https://ac.nowcoder.com/acm/contest/21289/C)**
**问题描述**
给定正整数$$a, b$$，和一个循环序列$$s\_{0}, s\_{1}, \cdots, s\_{k-1}, \cdots$$，满足$$s\_{i} = s\_{i - k}$$
其中$$s\_{i} = \pm 1$$，给定$$n$$，求$$\sum\_{i = 0}^{n} s\_{i}a^{n-i}b^{i} (\bmod 1e9 + 9)$$

**算法分析**
就是一个简单的推式子的题目
```math
\displaystyle
\sum_{i = 0}^{n} S_i a^{n-i}b^i = a^n \sum_{i = 0}^{n}S_i (b \cdot a^{-1})^i
```
令$$x = (b \cdot a^{-1}) (\bmod P)$$，可以写成
```math
\displaystyle
a^n \cdot \sum_{i = 0}^{n} S_i \cdot (x)^i \\
\quad \\

\Rightarrow S_0x^0 + S_1x^1 + \cdots + S_{k-1}x^{k-1} + \\
S_0x^{0+k} + S_1x^{1+k} + \cdots + S_{k-1}x^{2k-1} + \\
\vdots \\
\cdots \cdots + S_{k-1}x^{\lfloor \frac{n}{k} \rfloor - 1} \\
+ S_0x^{\lfloor \frac{n}{k} \rfloor \cdot k} + \cdots + S_nx^n 
```

考虑暴力求$$sum = S\_0x^0 + S\_1x^1 + \cdots + S\_{k-1}x^{k-1}$$，另外$$tail = S\_0x^{\lfloor \frac{n}{k} \rfloor \cdot k} + \cdots + S\_nx^n $$

这样就比较容易求了
原式可以写成
```math
sum \cdot ((x^k)^{0} +(x^k)^{1} + \cdots + (x^k)^{\lfloor\frac{n}{k} \rfloor - 1})
```

如果$$x^k \equiv 1(\bmod P)$$，那么答案是$$sum \cdot \lfloor \dfrac{n}{k} \rfloor $$

否则的话，令$$q = x^k$$，答案是$$sum \cdot \dfrac{1-q^{\lfloor \frac{n}{k} \rfloor}}{1-q}$$

```bash
void solve(int cas) {
    using Z = DynModInt<0>;
    Z::setMod(P);
    
    int n, _a, _b, k;
    cin >> n >> _a >> _b >> k;
    string str;
    cin >> str;

vector<int> s(k, 0);
    for (int i = 0; i < k; i++) {
        s[i] = (str[i] == '-' ? -1 : 1);
    }

Z a = _a, b = _b;
    Z x = b / a, coef = power(a, n);

Z tail = 0;
    for (int i = 0, j = (n / k) * k; j <= n; i++, j++) {
        Z now = s[i] * power(x, j);
        tail += now;
    }

Z sum = 0;
    for (int i = 0; i < k; i++) {
        Z now = s[i] * power(x, i);
        sum += now;
    }

Z q = power(x, k);
    Z res = 0;

if (q == Z(1)) {
        res = sum * Z(n / k);
    }
    else {
        res = sum * (1 - power(q, n /k)) / Z(1 - q);
    }

Z ans = coef * (res + tail);
    cout << ans << "\n";
}
```

## Lucas 定理
对于很大的素数$$p$$，我们有
```math
\displaystyle
\binom{n}{k} \equiv \binom{\lfloor n / p \rfloor}{\lfloor k/p  \rfloor} \cdot \binom{n \bmod p}{k \bmod p} (\bmod p)
```
其中当$$n < k$$时，二项式系数规定为$$0$$

> 生成函数证明
前置定理，费马小定理，$$a^{p} \equiv a (\bmod p)$$，这是因为$$a^{p-1} \equiv 1(\bmod p)$$
从而有$$a^{p} \equiv a (\bmod p)$$
另外还要证明一个结论，对于$$p$$的倍数，二项式展开，当且仅当$$n = 0$$或者$$n = p$$时候，$$\binom{p}{n} = 1$$，其他情况都是`0`

> 形式化地
```math
\displaystyle
\binom{p}{n} \equiv [n = 0 \cup n = p] (\bmod p)
```

> 我们构造生成函数$$f(x) = ax^n + bx^m$$
```math
\displaystyle
(f(x))^p = (ax^n + bx^m)^p \\
=\sum_{k = 0}^{p} \binom{p}{k} (ax^n)^k (bx^m)^{p-k} \\
\equiv a^px^{pn} + b^p x^{pm} \\
\equiv a(x^p)^n + b(x^p)^m = f(x^p) (\bmod p)
```

> 那么对于
```math
\displaystyle
(1+x)^n = (1+x)^{p \cdot \lfloor n / p \rfloor} \cdot (1 + x)^{n \bmod p} \\
\equiv (1 + x^p)^{\lfloor n / p \rfloor} \cdot (1 + x)^{n \bmod p} (\bmod p)
```
考虑关于$$x^k$$的项，不难发现，右边第一项，$$x$$的幂次一定是$$p$$的倍数
形如$$k = p \cdot \lfloor \dfrac{k}{p} \rfloor + k \bmod p$$

> 那么$$\lfloor \dfrac{k}{p} \rfloor$$是第一项贡献，$$k \bmod p$$第二项贡献
```math
\displaystyle
\binom{\lfloor n / p \rfloor}{\lfloor k/p  \rfloor} \cdot \binom{n \bmod p}{k \bmod p} (\bmod p)
```
对应右边的系数

### 数列计数
**[2025“钉耙编程”中国大学生算法设计春季联赛3 数列计数](https://acm.hdu.edu.cn/contest/problem?cid=1152&pid=1001)**
给定长度为$$n$$的数组$$a, L$$，问有多少长度为$$n$$的数组$$b_1, b_2, \cdots, b_n$$满足
```math
\displaystyle
0 \leqslant b_i \leqslant L_i \\
\prod_{i = 1}^{n} \binom{a_i}{b_i} \bmod 2 = 1
```

**算法分析**
注意到
```math
\displaystyle
\prod \binom{a_i}{b_i} \bmod 2 \equiv \prod \binom{a_i / 2}{b_i / 2} \binom{a_i \bmod 2}{b_i \bmod 2}
```
这就很显然了，对$$a_i$$，一位一位来看，只要$$\binom{a_i}{b_i} = \binom{0}{1} = 0$$那么一定不合法
也就是说，如果$$a_i$$某一位是$$1$$，那么$$b_i$$可以任意取，否则呢？$$a_i$$在某一位是$$0$$，
这时候，$$b_i$$在这一位就只能取$$0$$，然后统计答案即可

> 那现在的问题是，怎么考虑$$\leqslant L_i$$的限制？

**这是非常典型的数位 dp**
```bash
void solve() {
    const int LOG = 30;
    vector dp(LOG+5, vector<mint>(2, 0));

auto dfs = [&](auto &dfs, const int ai, const int li, int i, int smaller) -> mint {
        mint &ans = dp[i][smaller];
        if (i < 0) {
            return mint(1);
        }
        if (dp[i][smaller].val() > 0) return ans;

mint res = 0;
        int hi = (smaller || (li >> i & 1)) ? 1 : 0;

for (int j = 0; j <= hi; j++) {
            if (j == 0) {
                res += dfs(dfs, ai, li, i - 1, smaller | (j < hi));
            }
            else {
                int bit = (ai >> i & 1);
                if (bit == 1) res += dfs(dfs, ai, li, i - 1, smaller | (j < hi));
            }
        }

return ans = res;
    };

mint ans = 1;
    for (int i = 1; i <= n; i++) {
        dp.assign(LOG+5, vector<mint>(2, 0));
        mint res = dfs(dfs, a[i], L[i], LOG, 0);

ans *= res;
    }
	
}
```

## 同余方程组
求方程组
```math
\begin{cases}
x \equiv a_1 (\bmod m_1) \\
x \equiv a_2 (\bmod m_2) \\
\vdots \\
x \equiv a_k (\bmod m_k)
\end{cases}
```
的解

> 先考虑$$k = 2$$的情况
如果展开，不难发现$$k_1m_1 - k_2m_2 = a_2 - a_1$$，可以用扩展欧几里得求出$$k_1, k_2$$
不难发现，有解当且仅当$$(m_1, m_2) \mid (a_2 - a_1)$$
解的形式是$$x \equiv x_0 (\bmod [m_1, m_2])$$，$$[m_1, m_2]$$表示最小公倍数

最后一步是怎么证明的呢？
> 实际上也不难，假设求出了一个解$$k_1 = y_1$$，那么
```math
\displaystyle
-y_1m_1 + y_2m_2 = a_1 - a_2 \\
-y_1 = y_{1, 0} + k \dfrac{m_2}{(m_1, m_2)}
\quad \\
\Rightarrow x = y_1m_1 + a_1 = m_1y_{1, 0} + k \dfrac{m_1m_2}{(m_1, m_2)} + a_1 \\
\Rightarrow x = x_0 + k \dfrac{m_1m_2}{(m_1, m_2)}
```

这样，我们就可以把$$k$$个同余方程转化为$$k-1$$个方程
最后同余方程组解的形式，必然是
```math
\displaystyle
x \equiv x_0 (\bmod [m_1, m_2, \cdots, m_k])
```

### CRT
**第一步**
考虑合并两个同余方程
```math
\begin{cases}
x \equiv r_0 (\bmod p_0) \\
x \equiv r_1 (\bmod p_1)
\end{cases}
\Rightarrow 
\begin{cases}
x = k_0p_0 + r_0 \\
x = k_1p_1 + r_1
\end{cases}
\Rightarrow
k_0p_0 - k_1p_1 + r_0 - r_1 = 0
```
从而有方程$$r_1 - r_0 = k_0^{\prime}p_0 - k_1^{\prime}p_1$$，可以考虑用扩展欧几里得，求出关于
```math
k_0p_0 - k_1p_1 = gcd(p_0, p_1)
```
的特解
```bash
[g, k0, k1] = exgcd(p0, p1)
```

**第二步**
构造$$x \equiv x_0 (\bmod [p_0, p_1])$$的形式

1）如果$$g \nmid (r_1 - r_0)$$，那么很显然无解
2）否则，$$k_0$$是一个特解，那么通解呢？令$$d = \dfrac{r_1 - r_0}{g}$$
$$(k_0p_0 - k_1p_1) \cdot d = r_1 - r_0$$就是一组通解

3）因为$$x = k_0^{\prime}p_0 + r_0$$，那么$$x = k_0 \cdot d \cdot p_0 + r_0$$
自然有$$x \equiv (k_0 \cdot d \cdot p_0 + r_0) (\bmod [p_0, p_1])$$

这时候，只要令$$p_0 \leftarrow [p_0, p_1]$$，同时$$r_0 \leftarrow (k_0 \cdot d \cdot p_0 + r_0)$$
然后继续迭代即可，迭代到最后，$$r_0$$就是一组合法的解

### 算法实现
```bash
void solve(int cas) {
    int n;
    cin >> n;

i128 p, r;
    cin >> p >> r;

for (int i = 1; i < n; i++) {
        i128 pi, ri;
        cin >> pi >> ri;

// kp - kipi = ri - r
        auto [g, k, ki] = exgcd(p, pi);
        if ((ri - r) % g != 0) {
            cout << "-1\n";
            return;
        }

i128 d = (ri - r) / g;
        i128 np = (p * pi) / g;
        i128 nr = (r + k * d % np * p % np) % np;

p = np, r = safeMod(nr, np);
    }

cout << r << "\n";
}
```
## 附：裴祖定理和扩展欧几里得的证明
设$$a, b$$是不全为$$0$$的整数，那么对于任意的整数$$x, y$$，均有$$gcd(a, b) \mid ax + by$$成立
而且，存在整数$$x, y$$，使得$$ax + by = gcd(a, b)$$成立

**证明是构造性的**
```math
\displaystyle
\begin{cases}
ax_1 + by_1 = gcd(a, b) \\
bx_2 + (a \bmod b)y_2 = gcd(b, a\bmod b)
\end{cases}
```
从而$$ax_1 + by_1 = bx_2 + (a \bmod b)y_2$$
也就是说$$\displaystyle ax_1 + by_1 = bx_2 + \left(a - \lfloor\dfrac{a}{b} \rfloor b \right)y_2$$
```math
\displaystyle
ax_1 + by_1 = ay_2 + b \left(x_2 - \lfloor \dfrac{a}{b} \rfloor y_2 \right) \\
\quad \\
(x_1, y_1) \to \left(y_2, x_2 - \lfloor\dfrac{a}{b} \rfloor y_2 \right)
```
不断递归下去，最后$$b = 0, a = 1$$，有$$x_1 = gcd(1, 0) = 1$$
从而有一个解$$(x, y) = (1, 0)$$，将递归返回，就可以得到裴祖定理的一组整数解

看完文章有啥想法

算法小站

wiki 主题

数学

同余与模的一些问题

目录