numberTheory

base

质数与因数分解

因数也称为约数, 是指能整除一个整数的数

• 例如: 的因数有
• 例如: 的因数有

分解一个数的所有因数

枚举解空间

复杂度为:

def divisor(n):
    res = [1, n]
    for i in range(1, n + 1):
        if n % i == 0:
            res.append(i)

试除法求所有因数

找到一个 约数 , 那么 也是一个约数

复杂度为:

def divisor(n):
    res = [1, n]
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            res.append(i) # 添加 $d$
            if i != n // i:
                res.append(n // i) # 添加 $n/d$
    return res

分解质因数

例如:

• , 即 有 2 和 3 两个质因数
• , 即 有 2, 3 和 5 三个质因数

# 试除法
def prime_factorization(n):
    res = []
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            count = 0
            while n % i == 0:
                n //= i
                count += 1
            res.append((i, count))
    if n > 1:
        res.append((n, 1))
    return res
print(prime_factorization(12))  # 输出: [(2, 2), (3, 1)]

余与模运算

快速幂运算

快速幂运算是计算 的一种高效方法，时间复杂度为

def fast_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:  # 如果 n 的最低位是 1 (n % 2 == 1)
            res *= a
        a *= a
        n >>= 1  # n //= 2
    return res

快速幂运算 + 模

def fast_pow_mod(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:  # 如果 n 的最低位是 1 (n % 2 == 1)
            res = (res * a) % mod
        a = (a * a) % mod
        n >>= 1  # n //= 2
    return res