同余运算
同余运算
问题描述
同余运算是处理模运算的重要工具，常用于大数运算、密码学等场景。基本运算包括快速幂、逆元等。
快速幂
算法思想
- 将指数转换为二进制表示
- 利用平方的性质快速计算
- 适用于大数幂运算
- 时间复杂度
代码实现
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
乘法逆元
算法思想
- 基于扩展欧几里得算法
- 费马小定理（当模数为质数时）
- 适用于除法取模运算
- 时间复杂度
代码实现
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};
}
};
时间复杂度分析
| 快速幂 | ||
| 乘法逆元 | ||
| 中国剩余定理 | ||
| 欧拉函数 |
应用场景
- 大数幂运算
- 模运算除法
- 密码学计算
- 组合数取模
- 线性同余方程
注意事项
- 溢出的处理
- 负数的处理
- 逆元存在性
- 模数的选择
- 运算顺序
常见变形
- 组合数取模
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
- 线性同余方程
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
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
