同余运算

问题描述

同余运算是处理模运算的重要工具，常用于大数运算、密码学等场景。基本运算包括快速幂、逆元等。

快速幂

算法思想

将指数转换为二进制表示
利用平方的性质快速计算
适用于大数幂运算
时间复杂度 $\mathcal{O}(\log n)$

代码实现

c++
java
python

class Solution {
public:
    long long quickPow(long long a, long long n, long long mod) {
        long long result = 1 % mod;
        a = (a % mod + mod) % mod;
        while (n > 0) {
            if (n & 1) {
                result = result * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }
        return result;
    }
};

class Solution {
    public long quickPow(long a, long n, long mod) {
        long result = 1 % mod;
        a = (a % mod + mod) % mod;
        while (n > 0) {
            if ((n & 1) == 1) {
                result = result * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }
        return result;
    }
}

class Solution:
    def quickPow(self, a: int, n: int, mod: int) -> int:
        result = 1 % mod
        a = (a % mod + mod) % mod
        while n > 0:
            if n & 1:
                result = result * a % mod
            a = a * a % mod
            n >>= 1
        return result

乘法逆元

算法思想

基于扩展欧几里得算法
费马小定理（当模数为质数时）
适用于除法取模运算
时间复杂度 $\mathcal{O}(\log n)$

代码实现

class Solution {
public:
    // 扩展欧几里得求逆元
    long long modInverse(long long a, long long m) {
        long long d, x, y;
        tie(d, x, y) = exgcd(a, m);
        return d == 1 ? (x % m + m) % m : -1;
    }
    
    // 快速幂求逆元（m为质数）
    long long modInversePrime(long long a, long long m) {
        return quickPow(a, m-2, m);
    }
    
private:
    tuple<long long, long long, long long> exgcd(long long a, long long b) {
        if (b == 0) return {a, 1, 0};
        int d, x, y;
        tie(d, x, y) = exgcd(b, a % b);
        return {d, y, x - (a / b) * y};
    }
};

时间复杂度分析

算法时间复杂度空间复杂度

快速幂	$\mathcal{O}(\log n)$	$\mathcal{O}(1)$
乘法逆元	$\mathcal{O}(\log n)$	$\mathcal{O}(1)$
中国剩余定理	$\mathcal{O}(n \log n)$	$\mathcal{O}(n)$
欧拉函数	$\mathcal{O}(\sqrt{n})$	$\mathcal{O}(1)$

应用场景

大数幂运算
模运算除法
密码学计算
组合数取模
线性同余方程

注意事项

溢出的处理
负数的处理
逆元存在性
模数的选择
运算顺序

常见变形

组合数取模

cpp
java
python

class Solution {
public:
    // 预处理阶乘及其逆元
    vector<long long> fac, inv;
    void init(int n, long long mod) {
        fac.resize(n + 1);
        inv.resize(n + 1);
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i-1] * i % mod;
        }
        inv[n] = quickPow(fac[n], mod-2, mod);
        for (int i = n-1; i >= 0; i--) {
            inv[i] = inv[i+1] * (i+1) % mod;
        }
    }
    
    // 计算组合数C(n,k) mod p
    long long comb(int n, int k, long long mod) {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv[k] % mod * inv[n-k] % mod;
    }
};

class Solution {
    // 预处理阶乘及其逆元
    private long[] fac, inv;
    
    public void init(int n, long mod) {
        fac = new long[n + 1];
        inv = new long[n + 1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i-1] * i % mod;
        }
        inv[n] = quickPow(fac[n], mod-2, mod);
        for (int i = n-1; i >= 0; i--) {
            inv[i] = inv[i+1] * (i+1) % mod;
        }
    }
    
    // 计算组合数C(n,k) mod p
    public long comb(int n, int k, long mod) {
        if (k < 0 || k > n) return 0;
        return fac[n] * inv[k] % mod * inv[n-k] % mod;
    }
}

class Solution:
    def __init__(self):
        self.fac = []
        self.inv = []
    
    def init(self, n: int, mod: int) -> None:
        self.fac = [0] * (n + 1)
        self.inv = [0] * (n + 1)
        self.fac[0] = 1
        for i in range(1, n + 1):
            self.fac[i] = self.fac[i-1] * i % mod
        self.inv[n] = self.quickPow(self.fac[n], mod-2, mod)
        for i in range(n-1, -1, -1):
            self.inv[i] = self.inv[i+1] * (i+1) % mod
    
    def comb(self, n: int, k: int, mod: int) -> int:
        if k < 0 or k > n:
            return 0
        return self.fac[n] * self.inv[k] % mod * self.inv[n-k] % mod

线性同余方程

cpp
java
python

class Solution {
public:
    // 求解ax ≡ b (mod m)
    long long solveCongruence(long long a, long long b, long long m) {
        long long d, x, y;
        tie(d, x, y) = exgcd(a, m);
        if (b % d != 0) return -1;  // 无解
        x = x * (b / d) % m;
        return (x % m + m) % m;
    }
};

class Solution {
    // 求解ax ≡ b (mod m)
    public long solveCongruence(long a, long b, long m) {
        long[] result = exgcd(a, m);
        long d = result[0], x = result[1];
        if (b % d != 0) return -1;  // 无解
        x = x * (b / d) % m;
        return (x % m + m) % m;
    }
    
    private long[] exgcd(long a, long b) {
        if (b == 0) return new long[]{a, 1, 0};
        long[] result = exgcd(b, a % b);
        long d = result[0], x = result[1], y = result[2];
        return new long[]{d, y, x - (a / b) * y};
    }
}

class Solution:
    # 求解ax ≡ b (mod m)
    def solveCongruence(self, a: int, b: int, m: int) -> int:
        d, x, y = self.exgcd(a, m)
        if b % d != 0:
            return -1  # 无解
        x = x * (b // d) % m
        return (x % m + m) % m
    
    def exgcd(self, a: int, b: int) -> Tuple[int, int, int]:
        if b == 0:
            return a, 1, 0
        d, x, y = self.exgcd(b, a % b)
        return d, y, x - (a // b) * y