奇怪的逆元

· · 科技·工程

引理内容

这个公式似乎没有名字，我个人喜欢叫它逆元反转公式。

$$\text{inv}(a,b) = b - \frac {b \times \text{inv}(b,a) - 1} a$$ 其中 $\text{inv}(a,b)$ 指的是值域在 $[1,b)$ 中的 $a$ 的唯一模 $b$ 意义下乘法逆元。
看看怎么通过 $t$ 构造 $\text{inv}(a, b)$，我们尝试看看 $(a \times t) \bmod b$ 的值，发现是 $-1$。因此 $-t$ 是一个逆元。接下来研究 $t$ 的值域。 $t$ 最小是 $\frac {b-1} a \ge 1$；$t$ 最大是 $\frac {b (a-1) - 1} a = b - \frac {b-1} a \le b-1$。即 $t \in [1,b)$。 $-t \in (-b,-1]$，$b-t \in (0,b-1] = [1,b)$。不难发现，$b-t$ 就是 $\text{inv}(a,b)$ 的值，证毕。 ## 功能 - 首先是逆元反转。$a^{-1} \bmod b$ 不好处理的时候，可以反一下看看 $b^{-1} \bmod a$ 好不好。一般搭配题目特殊性质。 - 其次，很多时候我们天然关注逆元在群上的性质（即我们关心的是逆元等价类），而到了需要使用具体数值大小的时候就没有工具。这个公式限制了计算出的逆元大小。 # 例题 ## [2022 AMC12B Problem 23](https://artofproblemsolving.com/wiki/index.php/2022_AMC_10B_Problems/Problem_25) > 有一个无穷长 01 数组 $x$，你不知道它的值。 > > 有一个数列 $S_0 = x_0$，$S_n = S_{n-1} + x_n 2^n$。 > > 已知 $\forall n \ge 1$ 有 $7 S_n \equiv 1 \pmod {2^n}$。 > > 求 > > $$x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}$$ 看一下要求的东西，是 $\frac 1 {2^{2019}} (S_{2022} - S_{2018})$。 对于 $n \ge 1$ 有 $S_n \equiv \frac 1 7 \pmod {2^n}$，减掉 $x_n 2^n$ 即 $S_{n-1} \equiv \frac 1 7 \pmod {2^n}$。注意到 $S_{n-1} < 2^n$，因此 $S_{n-1} = \text{inv}(7, 2^n)$。 **逆元反转**： $$S_{n-1} = \text{inv}(7, 2^n) = 2^n - \frac {2^n \text{inv}(2^n, 7) - 1} 7 = 2^n - \frac {2^n (4^n \bmod 7) - 1} 7$$ 通项公式有了，后面就是简单体力活了。$4^n \bmod 7 = 4^{n \bmod 6} \bmod 7$ 加速计算。答案是 $\boxed{6}$。 ## [2023 AIME II Problem 15](https://artofproblemsolving.com/wiki/index.php/2023_AIME_II_Problems/Problem_15) > 对于正整数 $n$，定义 $a_n$ 为满足 $a_n \equiv 1 \pmod {2^n}$ 的最小正整数。 > > 求 $n \in [1,1000]$ 中有几个 $n$ 满足 $a_n = a_{n+1}$。 设 $a_n = 23 b_n$，那么 $b_n = \text{inv}(23, 2^n)$。然后我们就不管 $a_n$ 了，$a_n = a_{n+1}$ 等价于 $b_n = b_{n+1}$。 **逆元反转**： $$b_n = \text{inv}(23, 2^n) = 2^n - \frac {2^n \text{inv}(2^n, 23) - 1} {23} = 2^n - \frac {2^n (12^n \bmod 23) - 1} {23}$$ 只有 $\text{ord}(2,23) = 11$ 种可能。 那么暴力计算打出 $n = 0$ 到 $n = 11$ 的 $b_n$ 的表： $$b_{[0,11]} = \langle 1, 1, 3, 7, 7, 7, 39, 39, 167, 423, 935, 1959 \rangle$$ 观察其中 $n=0$ 到 $n=10$ 的部分，由周期性可知，在 $n \bmod 11 \in \{0, 3, 4, 6\}$ 时，$b_n = b_{n+1}$。 后面简单了，$1000 = 90 \times 11 + 10$，答案 $\boxed{363}$。 # References - [Short modular inverse - _h_](https://codeforces.com/blog/entry/23365) - [笔记——奇怪的逆元 - UnyieldingTrilobite](https://www.luogu.com/article/3amp2370)