进阶数论

进阶数论

1. 快速幂

1.1 核心思想

• 若 $b$ 为偶数：$a^b=(a^{b/2})^2$
• 若 $b$ 为奇数：$a^b=a\cdot a^{b-1}$

在取模场景中常用：计算 $a^b\bmod m$。



1.2 时间复杂度



$O(\log b)$



1.3 模板（取模快速幂）





long long qpow(long long a, long long n, long long p)  // 求 a^b  % p 的结果
{
    ll ans = 1;
    while (n)
    {
        if (n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}





---



2. 逆元





2.1 定义



若存在整数 $x$ 使得：

$$ a\cdot x\equiv 1\pmod m $$

则称 $x$ 是 $a$ 在模 $m$ 意义下的逆元，记作 $a^{-1}$。



2.2 逆元存在条件



当且仅当 $\gcd(a,m)=1$ 时逆元存在。

---



2.3 求逆元方法一：费马小定理（模为质数）



若 $m$ 是质数且 $a\not\equiv 0\pmod m$，则：

$$ a^{m-1}\equiv 1\pmod m $$

所以：

$$ a^{-1}\equiv a^{m-2}\pmod m $$



long long inv_prime_mod(long long a, long long p) { // p 是质数
    return qpow(a, p - 2, p);
}



---



2.4 求逆元方法二：扩展欧几里得（通用）



若 $\gcd(a,m)=1$，扩欧可求出：

$$ ax+my=1 $$

那么 $x\bmod m$ 就是逆元。



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 x1, y1;
    long long g = exgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

long long inv_general(long long a, long long mod) {
    long long x, y;
    long long g = exgcd(a, mod, x, y);
    // 需要保证 g == 1
    x %= mod;
    if (x < 0) x += mod;
    return x;
}



---



3. 扩展欧几里得





3.1 目标



不仅求 $\gcd(a,b)$，还要求一组系数 $(x,y)$ 满足：

$$ ax+by=\gcd(a,b) $$



3.2 重要结论：线性同余方程



求解：

$$ ax\equiv c\pmod m $$

等价于：

$$ ax+my=c $$

• 有解条件：$\gcd(a,m)\mid c$
• 若 $g=\gcd(a,m)$，可化简：

$$ \frac{a}{g}x\equiv \frac{c}{g}\pmod{\frac{m}{g}} $$



3.3 求最小正解步骤（常用套路）



1. 用扩欧求 $a'x+m'y=1$（其中 $a'=\frac{a}{g},m'=\frac{m}{g}$）
2. 得到 $a'^{-1}\equiv x\pmod{m'}$
3. $x_0\equiv \frac{c}{g}\cdot a'^{-1}\pmod{m'}$

---



4. 中国剩余定理（CRT）





4.1 问题形式



求整数 $x$ 满足：

$$ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \cdots\\ x\equiv a_k\pmod{m_k} \end{cases} $$

---



4.2 互质 CRT





结论



若 $m_1,m_2,\dots,m_k$ 两两互质，则模 $M=m_1m_2\cdots m_k$ 下解唯一。

构造方法：

• $M=\prod m_i$
• $M_i=\frac{M}{m_i}$
• $t_i=M_i^{-1}\pmod{m_i}$
• 答案：