逆元

数学归纳法初步

数学归纳法是一种证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。

核心思想： 如果某件事对第一个人成立，并且对第 $k$ 个人成立就能推出对第 $k+1$ 个人也成立，那么它对所有人都成立。

通俗类比： 排队推多米诺骨牌：

• 一个骨牌倒下了（验证起始）
• 每个倒下的骨牌都会推倒下一个（归纳假设 + 推出下一步）
• 所有骨牌都会倒下（命题对所有 $n$ 成立）

---

步骤

要证明命题 $P(n)$ 对所有 $n \geq 1$ 成立，通常需要两步：

• 第一步：验证基础（Base Case）

验证命题 $P(1)$ 成立。

• 第二步：归纳步骤（Inductive Step）

假设 $P(k)$ 成立（归纳假设），证明 $P(k+1)$ 也成立。

若上述两步都成立，则根据数学归纳法，$P(n)$ 对所有正整数 $n$ 成立。

---

例题

等差数列求和公式

用数学归纳法证明：

\[ 1 + 2 + \dots + n = \dfrac{n(n+1)}{2} \]

步骤一（基础情况）：当 $n=1$ 时，

\[ 1 = \dfrac{1(1+1)}{2} = 1 \quad \text{✅ 成立} \]

步骤二（归纳假设）：

假设对某个 $k$ 成立：

\[ 1 + 2 + \dots + k = \dfrac{k(k+1)}{2} \]

要证 $k+1$ 成立，即证明

\[ 1 + 2 + \dots + k + (k+1) = \dfrac{(k+1)(k+2)}{2} \]

左边根据假设变为：

\[ \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k + 2)}{2} \]

归纳成功！结论成立。

---

例题：$2^n \ge n+1$ 且 $n\geq 1$

用数学归纳法证明：

\[ 2^n \ge n+1, \quad \text{对所有 } n \ge 1 \text{ 成立} \]

基础情况：$n = 1$ 时：

\[ 2^1 = 2 \ge 2 = 1 + 1 \quad \text{✅ 成立} \]

归纳假设：假设 $2^k \ge k+1$

要证明：

\[ 2^{k+1} \ge k + 2 \]

左边：

\[ 2^{k+1} = 2 \cdot 2^k \ge 2(k + 1) \]

只需证 $2(k + 1) \ge k + 2$，即：

\[ 2k + 2 \ge k + 2 \Rightarrow k \ge 0 \quad \text{✅ 恒成立} \]

所以 $2^{k+1} \ge k + 2$ 成立。

证明完毕。

---

总结

• 忘记验证基础情况：必须先验证 $n=1$（或指定起点）。
• 归纳假设使用错误： 只能假设 $P(k)$ 成立，不可假设 $P(k+1)$。
• 推理逻辑不清晰： 归纳步骤中需逻辑严密地推出 $P(k+1)$。
• 对非整数使用归纳法： 归纳法只适用于正整数或可枚举集合。

---

小练习

使用数学归纳法证明：若 $p$ 为素数，$\gcd(a, p) = 1$，则 $a^{p} \equiv a \pmod{p}$。

• 验证 $a=1$ 的情况

显然 $1^p\equiv 1\pmod p$

前置证明

若 $p$ 为素数，证明在模 $p$ 意义下

\[ \binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p \]

根据组合数公式可得

\[ \binom{p}{i}=\dfrac{p!}{i!\times (p-i)!}=\dfrac{(p-i+1)\times (p-i+2)\times \ldots \times p}{1\times 2\times \ldots \times i},\ i\in [1,p-1] \]

由于 $p$ 是素数，因此 $1\sim p$ 中只有 $p\equiv 0\bmod p$。因此可得

\[ \binom{p}{i}\equiv 0\bmod p,\ i\in [1,p-1] \]

• 归纳假设

假设 $a^p\equiv a\pmod p$ 成立，那么通过二项式定理有

\[\begin{aligned} &(a+1)^p\\ =&\sum\limits_{i=0}^p \binom{p}{i} a^{p-i}\cdot 1^i\\ =&a^p+\binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\cdots +\binom{p}{p-1}a+1 \end{aligned}\]

由于 $p$ 为素数，在模 $p$ 意义下

\[ \binom{p}{1}\equiv \binom{p}{2}\equiv \cdots \equiv \binom{p}{p-1}\equiv 0\pmod p \]

因此 $(a+1)^p\equiv a^p+1 \pmod p$。

将 $a^p\equiv a\pmod p$ 带入得 $(a+1)^p\equiv a+1\pmod p$ 得证。

---

逆元

引入

• 向前走 $3$ 步，再向后走 $3$ 步，就回到了原点。
• 吃了 $5$ 颗糖，想 “回到原来”，就要 “不吃” $5$ 颗。
• 这些操作都是“互相抵消”的。

加法中的 逆

\[ 5 + (-5) = 0 \]

• 我们把 $-5$ 称为 $5$ 的 加法逆元。
• 加法逆元的作用是：让结果变成 $0$。

如果 $a + b = 0$，我们称 $b$ 是 $a$ 的加法逆元。

乘法中的 逆

\[ 4 \times \frac{1}{4} = 1 \]

• $\frac{1}{4}$ 是 $4$ 的乘法逆元。
• 乘法逆元的作用是：让结果变成 $1$。

如果 $a \cdot b = 1$，我们称 $b$ 是 $a$ 的乘法逆元。

---

定义

模意义下的逆元

若存在整数 $x$，使得：

\[ a \cdot x \equiv 1 \pmod{m} \]

则称 $x$ 是 $a$ 关于模 $m$ 的乘法逆元。

逆元存在的条件

• 不是每个数都有逆元！
• 当且仅当 $\gcd(a, m) = 1$，逆元才存在。

即当满足 $\gcd(a, m) = 1$，则存在整数 $x$，使得：

\[ a \cdot x \equiv 1 \pmod{m} \]

---

逆元的存在性证明

反证法： 设 $a$ 与 $b$ 不互素，即 $\gcd(a, b) = d \ne 1$，我们试图证明此时逆元不存在。

假设： 存在 $x$ 使得：

\[ ax \equiv 1 \pmod{b} \quad \Rightarrow \quad ax = kb + 1 \quad \text{对于某个整数 } \ k \ \text{成立} \]

两边同时除以 $d$ 得：

\[ \frac{ax}{d} = \frac{kb + 1}{d} \]

注意到：

• $d \mid a$ 且 $d \mid b$，所以 $\dfrac{ax}{d}$ 和 $\dfrac{kb}{d}$ 都是整数；
• 然而 $\dfrac{1}{d}$ 不是整数（因为 $d > 1$）。

矛盾： 左边为整数，右边含非整数项 $\frac{1}{d}$！

---

性质

• 逆元在模 $p$ 下是唯一的。

证明思路： 若 $i_1$ 和 $i_2$ 都是 $x$ 的逆元，则：

\[ x \cdot i_1 \equiv 1 \pmod{p}, \quad x \cdot i_2 \equiv 1 \pmod{p} \]

两式相等，左边相等，得：

\[ x(i_1 - i_2) \equiv 0 \pmod{p} \]

由于 $\gcd(x, p) = 1$，可约去 $x$，得：

\[ i_1 \equiv i_2 \pmod{p} \]

即逆元唯一（模意义下唯一）。

• 模质数 $p$ 下，$1 \sim p-1$ 中每个数都有唯一逆元，且两两不同。
  • 模 $p$ 下，逆元构成一个置换。
• 逆元的逆元是其本身：

\[ \text{若 }\ a^{-1} \equiv x \pmod{p} \text{，则 }\ x^{-1} \equiv a \pmod{p} \]

说明： 因为 $a \cdot x \equiv 1$，两边互换即得结论。

---

能干什么？

例如：在模 $7$ 意义下，求 $3$ 的乘法逆元。

• 哪个数乘以 $3$，模 $7$ 后等于 $1$？
• 尝试：$3 \times 1 = 3$, $3 \times 2 = 6$, $3 \times 5 = 15 \equiv 1$

\[ \boxed{3^{-1} \equiv 5 \pmod{7}} \]

换句话来说，在模 $7$ 意义下，除以 $3$ 和乘以 $5$ 等价！

---

逆元的求法

分类

前提条件： 一个数 $x$ 在模 $p$ 下存在逆元 $\iff \gcd(x,\ p) = 1$。

解法分类：

• 针对单个数字的逆元，存在两种 $\log$ 复杂度内的解法。
  • 一种方法针对模数是大质数，且 $x<p$，这样可以保证 $\gcd(x,p)=1$。
  • 一种方法只要求 $\gcd(x,p)=1$，需要使用 exgcd 算法。
• 针对 $n$ 个数字的逆元，存在 $O(n)$ 的解决办法。

---

费马小定理

当模数 $p$ 是质数时，可用费马小定理快速求逆元。

费马小定理：若 $p$ 是质数，且 $\gcd(a, p) = 1$，则：

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

两边同时除以 $a$，可得：

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

结论： 只需使用快速幂求出 $a^{p-2} \bmod p$ 即可。

---

时间复杂度：$O(\log{p})$，适用于绝大多数情况。前提 $p\nmid a$。

long long ksm(long long a, long long b, long long p) 
{
    long long res = 1;
    while (b) 
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
long long inv(long long a, long long p) 
{
    return ksm(a, p - 2, p); // 费马小定理
}

当模数很大时，普通乘法可能导致 $\texttt{long long}$ 溢出。

可使用 $\texttt{__int128}$ 类型做中间转换，避免溢出。

---

扩展欧几里得

要在模 $p$ 意义下求 $x^{-1}$，即找到一个整数 $x^{-1}$ 满足：

\[ x \cdot x^{-1} \equiv 1 \pmod{p} \]

将同余式转化为等式，有：

\[ x \cdot x^{-1} + p \cdot k = 1 \quad (k \in \mathbb{Z}) \]

这是一个形如：

\[ ax + by = \gcd(a, b) \]

的 线性不定方程，可通过 扩展欧几里得算法 解得一组整数解 $(x^{-1}, k)$。

注意： 若 $\gcd(x, p) \ne 1$，方程无整数解，逆元也不存在。

时间复杂度：$O(\log{p})$

long long exgcd(long long a, long long b, long long &x, long long &y) 
{
    if (b == 0) 
    {
        x = 1, y = 0;
        return a;
    }
    long long d = exgcd(b, a % b, x, y);
    long long t = x; 
    x = y; 
    y = t - a / b * y;
    return d;
}
long long inv(long long a, long long b) 
{
    long long x, y;
    exgcd(a, b, x, y); 
    x = (x % b + b) % b; 
    return x;
}

---

线性预处理逆元

问题背景： 若模数 $p$ 是质数，且我们需要频繁求 $1\sim n$（$n< p$） 中每个数的逆元，使用快速幂会有 $O(n\log p)$ 的复杂度。

目标： 使用线性递推，在 $O(n)$ 时间内预处理所有逆元。

递推公式：

\[ \boxed{ \texttt{inv[1]} = 1,\quad \texttt{inv[i]} = (p - \lfloor \frac{p}{i} \rfloor) \cdot \texttt{inv}[p \bmod i] \bmod p } \]

或者写作：

\[ \texttt{inv[i]} \equiv - \left\lfloor \frac{p}{i} \right\rfloor \cdot \texttt{inv}[p \bmod i] \pmod{p} \]

时间复杂度： $O(n)$

---

证明

已知：$p = ki + r$，其中 $i\in [1, n]$ 即

\[ ki + r \equiv 0 \pmod{p} \]

将等式两边同时乘以 $i^{-1} \cdot r^{-1}$，得到：

\[ k \cdot r^{-1} + i^{-1} \equiv 0 \pmod{p} \Rightarrow i^{-1} \equiv -k \cdot r^{-1} \pmod{p} \]

由此得出：

\[ \boxed{ \texttt{inv[i]} \equiv - \left\lfloor \frac{p}{i} \right\rfloor \cdot \texttt{inv}[p \bmod i] \pmod{p} } \]

直观理解： 利用较小数的逆元递推出较大的逆元。

---

constexpr int N = 3e6 + 5;
int inv[N], p;
void init(int n) 
{
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) 
    {
        inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
    }
}

该方法要求 $p$ 是质数，保证 $n<p$ 都有逆元；

---

问题背景： 给定 $n$ 个整数 $a_1,a_2,\ldots,a_n$，求它们在模 $p$ 下的逆元。保证所有 $a_i < p$。为避免输出过多，请求出 $\sum\limits_{i=1}^n \dfrac{k^i}{a_i}$ 的值。其中 $n\leq 5\times 10^6$。

方法：

• 预处理 $k[i]$ 表示 $k^i$，根据 $k^i=k^{i-1}\times k$ 递推求得即可。时间复杂度：$O(n)$。

则问题的难点在于如何线性求出 $a_i$ 的逆元。

利用前缀积逆元的递推关系求逆元。

设 $s_i = a_1\times a_2\times \ldots \times a_i \pmod p$，其中 $s_0=1$。

则有逆元关系：

\[ s_i^{-1} = s_{i+1}^{-1} \times a_{i+1} \pmod p \]

这来源于分数约分：分子分母同乘除一个 $a_{i+1}$。

$\dfrac{1}{s_i}=\dfrac{1}{s_{i+1}}\times a_{i+1}$。

$s_i=a_1\times a_2\times \ldots \times a_i \pmod p$。

$s_{i+1}=a_1\times a_2\times \ldots \times a_i\times a_{i+1} \pmod p$。

有了 $s_i$ 以及 $s_{i}^{-1}$ 以后，就可以求解 $a_i^{-1}$ 了。

根据 $a_i=\dfrac{s_{i-1}}{s_i}=s^{i-1}\times s_i^{-1}$ 可以正常求出每一项。

具体流程

• 计算 $k^i$ 保存到数组 $k[i]$ 中。
• 计算前缀积 $s_i = s_{i-1} \times a_i \pmod p$ 保存到数组 $s[i]$ 中。
• 求出总积逆元 $s_n^{-1}$ 保存到数组 $invs[n]$ 中，本题可以用费马小定理求出。
• 逆序递推计算 $i\in [n-1,0]$ 时其余 $s_i^{-1}$ 保存到数组 $invs[n-1]\sim invs[0]$ 中。
• 遍历 $1\sim n$ 求解所有 $a_i^{-1}$ 的同时顺便求解答案。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e6 + 5; 
int n, p, K, a[N], k[N], s[N], invs[N];
int read()
{
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
long long ksm(long long a, long long b)
{
    long long res = 1;
    while (b)
    {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res; 
}
int main()
{
    k[0] = 1;
    n = read(), p = read(), K = read();
    for (int i = 1; i <= n; i++) k[i] = 1ll * k[i - 1] * K % p;
    s[0] = 1; 
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        s[i] = 1ll * s[i - 1] * a[i] % p;
    }
    invs[n] = ksm(s[n], p - 2);// 初始化 s[n] 的逆元 
    for (int i = n - 1; i >= 0; i--)
        invs[i] = 1ll * invs[i + 1] * a[i + 1] % p; 
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        long long inva = 1ll * s[i - 1] * invs[i] % p; 
        ans = (ans + 1ll * k[i] * inva % p) % p;
    }
    cout << ans;
    return 0;
}