07_数论

数论

取整

# 向上取整到 k 的倍数
(n + k - 1) // k * k

import math
math.ceil(n / k) * k      # 更易读

# 四舍五入（整数版，避免浮点误差）
def round_div(a, b):
    # 计算 a / b，四舍五入到整数
    # 原理：判断小数部分是否 >= 0.5
    return a // b + (2 * (a % b) >= b)
# 示例：7 // 4 = 1，但 round_div(7, 4) = 2

# 四舍五入（浮点数版本）
n = float(input())
if n - int(n) >= 0.5:
    print(int(n) + 1)
else:
    print(int(n))

模运算

在模运算中，我们不是直接处理整数本身，而是处理它们除以 $m$ 后的余数（取模 $m$）。例如取 $m = 23$ 时，不处理 $x = 247$，而使用 $x \bmod 23 = 17$。

通常 $m$ 是一个大素数，题目给出；最常见的两个值是 $10^9 + 7$ 和 $998244353 = 119 \cdot 2^{23} + 1$。

模运算用于避免溢出内置数据类型的数字：

• $(a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m$
• $(a - b) \bmod m = ((a \bmod m) - (b \bmod m)) \bmod m$
• $(a \cdot b) \bmod m = ((a \bmod m) \cdot (b \bmod m)) \bmod m$
• $a^b \bmod m = (a \bmod m)^b \bmod m$

快速幂（模幂）

计算 $x^n \bmod m$，直接循环乘 $n$ 次是 $O(n)$，$n$ 达到 $10^9$ 时太慢。二进制幂把指数按二进制分解（如 $5^{10} = 5^{1010_2} = 5^8 \cdot 5^2$），复杂度降到 $O(\log n)$：

def pow_mod(a, b, mod):
    """计算 a^b mod mod"""
    res = 1
    a %= mod
    while b:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res

Python 内置 pow 就是快速幂，竞赛直接用：

MOD = 10**9 + 7
print(pow(first, second, MOD))

模逆元

模逆元相当于实数中的倒数：要计算 $a$ 除以 $b$（模意义下），就乘以 $b$ 的逆元。对素数模 $p$，$a$ 的逆元 $a^{-1}$ 满足：

$$a \cdot a^{-1} \equiv 1 \pmod{p}$$

例如 $2$ 模 $10^9 + 7$ 的逆元是 $i = \frac{p+1}{2} = 500000004$（验证：$2 \times 500000004 = 1000000008 \equiv 1$）。

费马小定理：不被 $p$ 整除的整数 $a$ 满足 $a^{p-1} \equiv 1 \pmod{p}$，因此 $a^{p-2} \cdot a \equiv 1$，即 $a^{p-2}$ 就是 $a$ 模 $p$ 的逆元：

MOD = 10**9 + 7

# 方法1：费马小定理
x = pow(2, MOD - 2, MOD)
print(x)  # 500000004
assert 2 * x % MOD == 1

扩展欧几里得同样可以求逆元（不要求模数为素数，只要求 $\gcd(a, m) = 1$）：

# 扩展欧几里得（求逆元）
def exgcd(a, b):
    if b == 0:
        return 1, 0, a
    x, y, g = exgcd(b, a % b)
    return y, x - (a // b) * y, g

def modinv(x, mod):
    """递归版扩展欧几里得求模逆元"""
    if x <= 1:
        return x
    return mod - mod // x * modinv(mod % x, mod) % mod

预计算逆元：频繁计算多个数的逆元时，用递推公式 $inv[i] = -(m / i) \cdot inv[m \bmod i] \bmod m$ 一遍预处理：

MOD = 10**9 + 7
inv = [0] * (N + 1)   # N 为需要的最大值，注意不要真开到 MOD
inv[1] = 1
for i in range(2, N + 1):
    inv[i] = MOD - MOD // i * inv[MOD % i] % MOD

组合数（预计算）

# 组合数（预计算）：计算组合数 C(n, k) = n! / (k!(n-k)!)
# - 使用：fact, inv_fact = comb_init(1000000, MOD)
#        print(C(100, 50, MOD, fact, inv_fact))
# - 注意：需要 MOD 为质数（常用 10^9+7）
def comb_init(n, mod):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % mod
    inv_fact = [1] * (n + 1)
    inv_fact[n] = pow(fact[n], mod-2, mod)
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % mod
    return fact, inv_fact

def C(n, k, mod, fact, inv_fact):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % mod * inv_fact[n-k] % mod

模运算注意事项

1. 除零错误：必须确保不尝试除以 0
2. 取模后的零：非零数取模后可能变成零，对非常数做除法时要格外小心
3. 性能：模逆元需要 $O(\log p)$，循环内频繁除法会显著变慢；同一个数的逆元多次使用时应预计算

素数

素数判断

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            return False
    return True

埃拉托斯特尼筛法（线性筛，求 minp）

minp = []
primes = []

def sieve(n: int):
    """埃拉托斯特尼筛法 - 计算 minp 和 primes"""
    global minp, primes
    minp = [0] * (n + 1)
    primes = []

    for i in range(2, n + 1):
        if minp[i] == 0:
            minp[i] = i
            primes.append(i)

        for p in primes:
            if i * p > n:
                break
            minp[i * p] = p
            if p == minp[i]:
                break

质因数分解

def prime_factors(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

约数

# 最大公约数 / 最小公倍数
g = math.gcd(a, b)
lcm = a * b // g

# 约数枚举：求出 n 的所有约数（因数），返回升序列表
def divisors(n):
    small, large = [], []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
    return small + large[::-1]

# 批量：返回 1 到 n 所有数的约数列表（O(n log n)，适合多次查询）
def get_divisors(n: int):
    divs = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            divs[j].append(i)
    return divs

约瑟夫环

# n 个人围成一圈，每数到 k 就淘汰一人，求最后存活者的初始位置
def josephus(n, k):
    if n == 1:
        return 0
    return (josephus(n-1, k) + k) % n

K 进制转换

# 数字 -> k进制字符串（每位对应字符集 s）
def idx_to_password(idx, k, m, s):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

# k进制字符串 -> 数字
def password_to_idx(password, k, s):
    idx = 0
    for ch in password:
        idx = idx * k + s.index(ch)
    return idx

位运算

1 << i           # 2^i（左移，i=3 → 8）
# 判断
x & (1 << k)     # 检查第 k 位是否为 1
x >> k & 1       # 获取第 k 位的值

x.bit_length()   # 整数的二进制位数（5→3, 1→1, 0→0）
x.bit_count()    # 二进制中 1 的个数

x & -x           # 最低位 1（获取二进制最低位的 1）
x | 1            # 将最低位设为 1
x & ~1           # 将最低位设为 0
x ^ 1            # 翻转最低位

# 遍历检查某一位
for i in range(bit_count):
    if (S >> i) & 1:  # 检查第 i 位是否为 1
        # 第 i 位为 1
        pass

# 设置
x | (1 << k)     # 将第 k 位设为 1
x & ~(1 << k)    # 将第 k 位设为 0
x ^ (1 << k)     # 翻转第 k 位

# 常用
x & (x - 1)      # 清除最低位的 1
x | (x - 1)      # 将最低位 0 变成 1
x ^ (x + 1)      # 获取最低位不同的数

# 子集枚举
for sub in range(mask + 1):
    sub = (sub - 1) & mask  # 枚举子集（不包括 0）

# 最低位 1 的位置
bit = (x & -x).bit_length() - 1