wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

数学

组合计数

二项式定理

生成函数（一）

FFT

多项式与形式幂级数

同余与模

同余与模的应用

同余与模的概念

[[ item.c ]]

同余与模的应用

## 一些问题
### Biorhythms
**[Biorhythms](https://ac.nowcoder.com/acm/contest/21289/E)**
问题描述，人的身体周期23天，情绪周期28天，智力周期33天，每个周期都有一个峰值
一个人的三重峰，指的是他在某一天同时达到了3个周期的峰值，给定一个人三个周期的峰值`p, e, i`
求他在日期$$d$$后的第一个三重峰

**算法分析**
转化成同余方程组的语言，就是求
```math
\begin{cases}
x \equiv p (\bmod 23) \\
x \equiv e (\bmod 28) \\
x \equiv i (\bmod 33)
\end{cases}
```
求出$$x \equiv x_0(\bmod [23, 28, 33])$$的一个特解，如果它$$< d$$，那么就令$$x + k[23, 28, 33]$$
使得解$$> d$$

> 特别地，这里$$lcm = 21252$$，而$$d$$最大只有`365`
所以$$x \leftarrow x + lcm$$一定是满足的解，那么从日期`d`开始，要再经过多少天呢？

```math
((x + lcm - d - 1) \bmod lcm) + 1
```
这样的表达式也特别适用于下标从`1`开始的情况，比如$$n$$开始再经过一天，怎么算？
```math
((n + 1 - 1) \bmod n) + 1, ((n + d - 1) \bmod n) + 1
```
对下标是`1`的循环节，同样适用

### 同余问题
**[D. GCD Table](https://codeforces.com/problemset/problem/338/D)**
给定正整数$$n, m$$，给定$$k$$个正整数$$a_1, a_2, \cdots, a_k$$
求是否存在$$1 \leqslant i \leqslant n, 1 \leqslant j \leqslant m - k + 1$$满足
$$a_1 = (i, j), a_2 = (i, j+1), \cdots, a_k = (i, j + k - 1)$$，表示 gcd
注意，实际上，对于$$a_p$$，我们要使得$$a_p = (i, j), i \in [1, n], j \in [p, m]$$

**算法分析**
不难发现，首先应该满足$$a_1 \mid i, a_1 \mid j$$，用同余的语言表示就是
```math
i \equiv 0(\bmod a_1) \quad j \equiv 0 (\bmod a_1)
```
综合起来，就是
```math
\begin{cases}
i \equiv 0 (\bmod a_1) \\
i \equiv 0 (\bmod a_2) \\
\vdots \\
i \equiv 0 (\bmod a_k)
\end{cases},\quad
\begin{cases}
j \equiv 0(\bmod a_1) \\
j+1 \equiv 0 (\bmod a_2) \\
\vdots \\
j + k - 1 \equiv 0 (\bmod a_k)
\end{cases}
\Rightarrow
\begin{cases}
j \equiv a_1 - 0 (\bmod a_1) \\
j \equiv a_2 - 1 (\bmod a_2) \\
\vdots \\
j \equiv a_k - (k - 1)(\bmod a_k)
\end{cases}
```
根据中国剩余定理，解同余方程，不难发现
```math
\begin{cases}
i \equiv 0 (\bmod [a_1, a_2, \cdots, a_k]) \\
j \equiv j_0 (\bmod [a_1, a_2, \cdots, a_k])
\end{cases}
```
可以求出$$j_0$$，不妨记$$L = lcm(a_1, a_2, \cdots, a_k)$$，那么有
```math
\begin{cases}
i = \{L, 2L, 3L, \cdots\} \\
j = \{j_0, j_0 + L, j_0 + 2L, \cdots\}
\end{cases}
```
注意到$$a_1 = (i, j) = (i = pL, \quad j = j_0 + qL), (\forall p, q \in \mathbb{N})$$

> 猜想，考虑$$(L, j_0)$$组合是否可行，能不能进一步推广到$$(pL, j_0 + qL)$$

```math
a_1 = (pL, j_0 + qL) \Rightarrow \begin{cases} a_1 \mid L \\ a_1 \mid j_0 \end{cases} \Rightarrow a_1 \mid (L, j_0)
```
另一方面，注意到$$(L, j_0) \mid (pL, j_0 + qL)$$
所以有$$a_1 \mid (L, j_0) \mid (pL, j_0 + qL) = a_1$$，所以只需要考虑$$(L, j_0)$$这一组即可
check 以下是否成立
```math
\begin{cases}
a_1 = (L, j_0) \\
a_2 = (L, j_0 + 1) \\
\vdots \\
a_k = (L, j_0 + k - 1)
\end{cases}
```

> 算法实现的时候，注意特判
特别注意一下，$$j \equiv j_0 (\bmod lcm[a_1, a_2, \cdots, a_k])$$时候，$$j_0 = 0$$的情况
此时我们让$$j_0 = (0 + lcm)$$

## 孙子定理，同余方程的构造解
**针对模数两两互质的情况**
设$$m_1, m_2, \cdots, m_k$$是两两互质的$$k$$个正整数，那么方程组
```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}
```
的解为
```math
\displaystyle
x \equiv \sum_{i = 1}^{k}M_i'M_ia_i (\bmod M)
```
其中$$M = m_1m_2\cdots m_k$$，$$M_i = M / m_i$$，$$M_i'M_i \equiv 1(\bmod m_i)$$

> 证明
![](/media/content_img/crt.png)

**一些应用**
比如说，我们要求这样一个同余方程$$f(x) \equiv 0(\bmod m)$$，$$f(x)$$是关于$$x$$的多项式
将$$m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$
```math
\begin{cases}
f(x) \equiv 0 (\bmod p_1^{\alpha_1}) \\
f(x) \equiv 0 (\bmod p_2^{\alpha_2}) \\
\vdots \\
f(x)  \equiv 0 (\bmod p_k^{\alpha_k})
\end{cases}
\Rightarrow
\begin{cases}
x \equiv r_1 (\bmod p_1^{\alpha_1}) \\
x \equiv r_2 (\bmod p_2^{\alpha_2}) \\
\vdots \\
x \equiv r_k (\bmod p_k^{\alpha_k})
\end{cases}
```
这样可以直接用孙子定理，构造出一个形如$$x \equiv \sum_i ? \cdot a_i (\bmod m)$$的解

## 扩展欧拉定理
扩展欧拉定理表述如下
```math
a^{b} (\bmod c) = \begin{cases} a^b (\bmod c) && b < \phi(c) \\ 
a^{b \bmod \phi(c) + \phi(c)} (\bmod c) && b \geqslant \phi(c)
\end{cases}
```

> 引理1
如果$$x \equiv y(\bmod p), x \equiv y (\bmod q), (p, q) = 1$$，那么有$$x \equiv y (\bmod pq)$$
因为$$(x - y) = k_1p, \quad (x-y) = k_2q$$，从而$$(x - y) = k \cdot lcm(p, q)$$
也就是说$$x \equiv y (\bmod lcm(p, q))$$，因为$$(p, q) = 1, lcm(p, q) = p \cdot q$$
从而有$$x \equiv y (\bmod pq)$$

尝试证明
考虑对$$c = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$，只需要证明
```math
a^b \equiv a^{b \bmod \phi(c) + \phi(c)} (\bmod p_i^{\alpha_i})
```
考虑以下两种情况
**a.**$$gcd(a, p_i^{\alpha_i}) = 1$$
根据朴素的欧拉定理，我们有$$a^{\phi(p_i^{\alpha_i})} \equiv 1 (\bmod p_i^{\alpha_i})$$
那么因为欧拉函数的积性，$$\phi(p_i^{\alpha_i}) \mid \phi(c)$$，从而$$a^{\phi(c)} \equiv 1(\bmod p_i^{\alpha_i})$$
> (这一步的证明是简单的，可以用二项式展开)

回到$$a^b$$，我们有
```math
a^b \equiv a^{\lfloor b / phi(c) \rfloor \cdot \phi(c)  + b \bmod \phi(c)} \\
\equiv a^{\lfloor b / phi(c) \rfloor \cdot \phi(c)} \cdot a^{b \bmod \phi(c)} \\
\equiv 1 \cdot a^{b \bmod \phi(c)} \equiv a^{\phi(c)} \cdot a^{b \bmod \phi(c)} \\
\equiv a^{b \bmod \phi(c) + \phi(c)} (\bmod p_i^{\alpha_i})
```

> 引理2
对于素数的幂$$p^x$$，必然有$$\phi(p^x) \geqslant x$$
不难发现$$\phi(p^x) = p^{x-1}(p - 1)$$关于$$p$$单调递增，$$\phi(p^x)\_{\min} \geqslant x$$成立即可
考虑$$\phi(2^x) \geqslant x$$是否成立呢？定义$$g(x) = 2^{x-1} - x$$随着$$x$$单调增，$$g(x) \geqslant 0$$恒成立
所以命题证毕

**b.**$$gcd(a, p_i^{\alpha_i}) \neq 1$$
那么我们有
```math
a^b = (np_i)^b = n^b p_i^b = n^b \cdot p_i^{b-\alpha_i} \cdot p_i^{\alpha_i}
```
其中最后一步的拆分，是因为$$b \geqslant \phi(c) \geqslant \phi(p_i^{\alpha_i}) \geqslant \alpha_i$$(引理2)
从而有$$p_i^{\alpha_i} \mid a^{b}$$，即
```math
a^b \equiv 0(\bmod p_i^{\alpha_i})
```

再看$$a^{b \bmod \phi(c) + \phi(c)}$$，转化如下
```math
a^{b \bmod \phi(c) + \phi(c)} = (np_i)^{b \bmod \phi(c) + \phi(c)} \\
= n^{b \bmod \phi(c) + \phi(c)} \cdot p_i^{b \bmod \phi(c) + \phi(c)} \\
= n^{b \bmod \phi(c) + \phi(c)}  \cdot p_i^{b \bmod \phi(c) + \phi(c) - \alpha_i} \cdot p_i^{\alpha_i}
```
从而我们有
```math
p_i^{\alpha_i} \mid a^{b \bmod \phi(c) + \phi(c)} \Rightarrow a^{b \bmod \phi(c) + \phi(c)} \equiv 0 (\bmod p_i^{\alpha_i})
```

于是我们有
```math
a^b \equiv a^{b \bmod \phi(c) + \phi(c)} (\bmod p_i^{\alpha_i})
```
根据欧拉函数的积性，扩展欧拉定理成立

### 扩展欧拉定理的应用
**[Notepad](https://codeforces.com/problemset/problem/17/D)**
**问题描述**
`b`进制下所有的`n`位数写到一个笔记本，每一页写下`c`个数，求最后一页写下多少个数

**算法分析**
先来推一下公式，所有的`n`位数，一共有多少种可能呢？
答案是$$(b - 1) \cdot b^{n}$$（首位只能填$$1 \sim b - 1$$）

最后一页的数，就是$$res = (b - 1) \cdot b^{n-1} \bmod c$$
**1.** 如果$$res = 0$$，最后一项就是$$c$$
**2.** $$((b - 1) \cdot b^{n - 1}) \bmod c = ((b - 1) \bmod c) \cdot (b^{n-1} \bmod c)$$
但这里，$$n$$是$$10^{10^6}$$级别的

如果$$n - 1 < \phi(c)$$，那么$$b^{n - 1} \bmod c$$可以直接计算，应该是$$(b \bmod c)^{n - 1}$$
这一步可以快速幂计算出来

如果$$n - 1 \geqslant \phi(c)$$，要用扩展欧拉定理，$$b^{n - 1} \bmod c \equiv b^{(n - 1) \bmod \phi(c) + \phi(c)} \bmod c$$
这部分的答案变成了$$(b \bmod c)^{(n-1) \bmod \phi(c) + \phi(c)}$$

**算法实现**
```bash
void solve(int cas) {
    string _b, _n;
    int c;
    cin >> _b >> _n >> c;

int phic = phi(c);

if (_n.size() <= 10 && std::stoll(_n) < phic) {
        i64 n = stoll(_n);
        BigInt b(_b);
        i64 part1 = powMod((b % c), n - 1, c);
        i64 part2 = (b - 1) % c;

i64 ans = part1 * part2 % c;
        if (ans == 0) ans = c;

cout << ans << "\n";
    }
    else {
        BigInt b(_b), n(_n);
        i64 part1 = powMod( (b % c) , ((n - 1) % phic) + phic,  c);
        i64 part2 = (b - 1) % c;

i64 ans = part1 * part2 % c;
        if (ans == 0) ans = c;
        cout << ans << "\n";
    }
}
```

### 扩展欧拉定理的应用2
**[D. Power Tower](https://codeforces.com/problemset/problem/906/D)**
定义序列`a[1...n]`的幂值为
```math
a_1^{\left(a_2^{ \left(a_3^{\cdots^{a_n}} \right) }  \right)}
```
现在给定正整数列$$w_1, w_2, \cdots, w_n$$，给定`q`个询问
询问序列$$w(l_k), \cdots, w(r_k)$$的幂对$$m$$取模的结果

**算法分析**
根据扩展欧拉定理
如果
```math
a_2^{\left( a_3^{\cdots^{a_n}} \right)} \geqslant \phi(m)
```
我们有
```math
\displaystyle
a_1^{\left(a_2^{ \left(a_3^{\cdots^{a_n}} \right) }  \right)} (\bmod m) \equiv a_1^{\left(a_2^{ \left(a_3^{\cdots^{a_n}} \right) }  \right) \bmod \phi(m)} (\bmod m) \\
\quad \\
\Rightarrow a_2^{ \left(a_3^{\cdots^{a_n}} \right) }   \bmod \phi(m) = ?
```
这样形成了如下的子问题
```math
([1, n], m) \to ([2, n], \phi(m)) \to ([3, n], \phi(\phi(m))) \to \cdots
```

注意到$$m \to \phi(m) \to \phi(\phi(m)) \to \cdots$$

如果$$m$$是偶数，那么$$m = 2^k \cdot p_1^{\alpha_1} p_2^{\alpha_2} \cdots $$
那么$$\phi(m) = 2^{k-1} \cdot p_1^{\alpha_1 - 1}(p_1 - 1) \cdots $$，不难发现$$\phi(m) \leqslant \dfrac{m}{2}$$

如果$$m$$是奇数，$$\phi(m) = (p_1 - 1)p_1^{\alpha_1 - 1} \cdots = 2^{k} \cdot C$$
同样也有$$\phi(m) \leqslant \dfrac{\phi(\phi(m))}{2}$$

这样就可以递归求解，直到$$\phi(m) = \phi(1) = 1$$
每次询问，关于$$m$$的递归，复杂度是$$O(\log m)$$的

至于$$\phi(m), \phi(\phi(m)), \cdots$$，可以预处理打表，总体复杂度可以在$$O(q \log m)$$内完成

> 坑点

这里涉及到扩展欧拉定理，对于$$a^x (\bmod M)$$
**1.** 如果$$x < M$$，$$a^x \to a^x (\bmod M)$$
**2.** 如果$$x \geqslant M$$，$$a^x \to a^{x \bmod M + M}$$

所以递归求幂指的时候，需要区分一下
```bash
auto eulerMod = [&](int x, int M) -> int {
	return x < M ? x : (x % M + M); 
};
```
快速幂的时候，将其换成 eulerMod 来求解即可
```bash
// a^x (mod M)
// if (x < M) return a^x (mod M), calc(x) -> calc(x)
// else return a^{ (x mod phi(M)) + phi(M) }, calc(x) -> calc(x mod phi(M) + phi(M))

constexpr i64 eulerMod(i64 x, i64 p) {
    if (x < p) return x;
    return x % p + p;
}

i64 powMod(i64 a, i64 b, i64 p) {
    i64 res = 1;
    for (; b; b /= 2, a = eulerMod(a * a, p)) {
        if (b % 2) res = eulerMod(res * a, p);
    }
    return res;
}

auto calc = [&](auto &calc, int l, int r, i64 mod) -> i64 {
    if (l >= r || mod == 1) {
        return eulerMod(a[l], mod);
    }

i64 pw = calc(calc, l+1, r, Phi[mod]);
    i64 res = powMod(a[l], pw, mod);
    return res;
};
```

看完文章有啥想法

算法小站

wiki 主题

数学

同余与模的应用

目录