数论基础（七）练习题目¶

章节概述¶

本章提供了从基础到竞赛级别的练习题目，帮助你巩固数论知识。建议按顺序完成，每道题都经过精心设计，涵盖了前面章节的所有知识点。

学习目标¶

巩固数论基础知识
提高算法实现能力
掌握数论问题的解题思路
准备算法竞赛

（一）基础练习¶

练习1：判断整除¶

题目：编写函数，判断一个数是否能被另一个数整除。

要求： - 处理除数为 0 的情况 - 返回布尔值

def is_divisible(a, b):
    """
    判断 a 是否能被 b 整除

    参数:
        a: 被除数
        b: 除数

    返回:
        bool: 如果能整除返回 True
    """
    # 你的代码
    pass

# 测试
assert is_divisible(12, 3) == True
assert is_divisible(12, 5) == False
assert is_divisible(0, 5) == True
assert is_divisible(5, 0) == False
print("✓ 练习1通过")

练习2：求约数¶

题目：编写函数，求一个数的所有约数。

要求： - 返回按升序排列的约数列表 - 时间复杂度 O(√n)

def get_divisors(n):
    """
    求 n 的所有约数

    参数:
        n: 正整数

    返回:
        list: 约数列表（升序）
    """
    # 你的代码
    pass

# 测试
assert get_divisors(12) == [1, 2, 3, 4, 6, 12]
assert get_divisors(16) == [1, 2, 4, 8, 16]
assert get_divisors(1) == [1]
print("✓ 练习2通过")

练习3：判断质数¶

题目：编写函数，判断一个数是否为质数。

要求： - 使用试除法 - 时间复杂度 O(√n)

def is_prime(n):
    """
    判断 n 是否为质数

    参数:
        n: 正整数

    返回:
        bool: 如果是质数返回 True
    """
    # 你的代码
    pass

# 测试
assert is_prime(2) == True
assert is_prime(17) == True
assert is_prime(15) == False
assert is_prime(1) == False
print("✓ 练习3通过")

练习4：求最大公约数¶

题目：编写函数，使用欧几里得算法求两个数的最大公约数。

要求： - 使用迭代或递归 - 时间复杂度 O(log min(a, b))

def gcd(a, b):
    """
    求最大公约数

    参数:
        a, b: 整数

    返回:
        int: 最大公约数
    """
    # 你的代码
    pass

# 测试
assert gcd(12, 18) == 6
assert gcd(15, 25) == 5
assert gcd(0, 5) == 5
assert gcd(17, 23) == 1
print("✓ 练习4通过")

练习5：求最小公倍数¶

题目：编写函数，求两个数的最小公倍数。

要求： - 利用 GCD 和 LCM 的关系

def lcm(a, b):
    """
    求最小公倍数

    参数:
        a, b: 正整数

    返回:
        int: 最小公倍数
    """
    # 你的代码
    pass

# 测试
assert lcm(12, 18) == 36
assert lcm(15, 25) == 75
assert lcm(4, 6) == 12
print("✓ 练习5通过")

练习6：快速幂¶

题目：编写函数，计算 a^b mod m。

要求： - 使用快速幂算法 - 时间复杂度 O(log b)

def mod_pow(a, b, m):
    """
    计算 a^b mod m

    参数:
        a: 底数
        b: 指数（非负整数）
        m: 模数

    返回:
        int: a^b mod m
    """
    # 你的代码
    pass

# 测试
assert mod_pow(2, 10, 1000) == 24
assert mod_pow(3, 100, 1000000007) == 976371285
assert mod_pow(5, 0, 100) == 1
print("✓ 练习6通过")

练习7：求模逆元¶

题目：编写函数，求 a 模 m 的逆元。

要求： - 使用扩展欧几里得算法 - 处理逆元不存在的情况

def mod_inverse(a, m):
    """
    求 a 模 m 的逆元

    参数:
        a: 整数
        m: 模数

    返回:
        int: 逆元（如果存在）
             None（如果不存在）
    """
    # 你的代码
    pass

# 测试
assert mod_inverse(3, 7) == 5
assert mod_inverse(10, 17) == 12
assert mod_inverse(6, 9) is None
print("✓ 练习7通过")

练习8：计算欧拉函数¶

题目：编写函数，计算欧拉函数 φ(n)。

要求： - 使用分解质因数法 - 时间复杂度 O(√n)

def euler_phi(n):
    """
    计算欧拉函数 φ(n)

    参数:
        n: 正整数

    返回:
        int: φ(n)
    """
    # 你的代码
    pass

# 测试
assert euler_phi(1) == 1
assert euler_phi(7) == 6
assert euler_phi(12) == 4
assert euler_phi(100) == 40
print("✓ 练习8通过")

（二）进阶练习¶

练习9：埃拉托斯特尼筛法¶

题目：编写函数，使用埃拉托斯特尼筛法求所有小于等于 n 的质数。

要求： - 时间复杂度 O(n log log n) - 空间复杂度 O(n)

def sieve_of_eratosthenes(n):
    """
    埃拉托斯特尼筛法

    参数:
        n: 正整数

    返回:
        list: 小于等于 n 的所有质数
    """
    # 你的代码
    pass

# 测试
assert sieve_of_eratosthenes(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
assert sieve_of_eratosthenes(10) == [2, 3, 5, 7]
assert sieve_of_eratosthenes(1) == []
print("✓ 练习9通过")

练习10：线性筛法¶

题目：编写函数，使用线性筛法求所有小于等于 n 的质数。

要求： - 时间复杂度 O(n) - 每个合数只被标记一次

def linear_sieve(n):
    """
    线性筛法

    参数:
        n: 正整数

    返回:
        list: 小于等于 n 的所有质数
    """
    # 你的代码
    pass

# 测试
assert linear_sieve(30) == [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print("✓ 练习10通过")

练习11：求解线性同余方程¶

题目：编写函数，求解线性同余方程 a × x ≡ b (mod m)。

要求： - 返回所有解（在 [0, m-1] 范围内） - 处理无解的情况

def solve_linear_congruence(a, b, m):
    """
    求解线性同余方程 a × x ≡ b (mod m)

    参数:
        a, b: 整数
        m: 模数

    返回:
        list: 所有解（升序）
              空列表（无解）
    """
    # 你的代码
    pass

# 测试
assert solve_linear_congruence(3, 5, 7) == [4]
assert solve_linear_congruence(2, 4, 6) == [2, 5]
assert solve_linear_congruence(4, 3, 6) == []
print("✓ 练习11通过")

练习12：中国剩余定理¶

题目：编写函数，使用中国剩余定理解同余方程组。

要求： - 处理两两互质的模数 - 返回最小正整数解

def crt(equations):
    """
    中国剩余定理

    参数:
        equations: [(a₁, m₁), (a₂, m₂), ...]

    返回:
        tuple: (解, 模数)
               (None, None) 如果无解
    """
    # 你的代码
    pass

# 测试
equations = [(2, 3), (3, 5), (2, 7)]
solution, modulus = crt(equations)
assert solution == 23
assert modulus == 105
print("✓ 练习12通过")

练习13：质因数分解¶

题目：编写函数，对整数进行质因数分解。

要求： - 返回字典：{质数: 指数} - 使用试除法

def prime_factorization(n):
    """
    质因数分解

    参数:
        n: 正整数

    返回:
        dict: {质数: 指数}
    """
    # 你的代码
    pass

# 测试
assert prime_factorization(12) == {2: 2, 3: 1}
assert prime_factorization(100) == {2: 2, 5: 2}
assert prime_factorization(17) == {17: 1}
print("✓ 练习13通过")

练习14：计算莫比乌斯函数¶

题目：编写函数，计算莫比乌斯函数 μ(n)。

要求： - 正确处理各种情况 - 返回 -1, 0, 或 1

def mobius(n):
    """
    计算莫比乌斯函数 μ(n)

    参数:
        n: 正整数

    返回:
        int: μ(n)
    """
    # 你的代码
    pass

# 测试
assert mobius(1) == 1
assert mobius(2) == -1
assert mobius(4) == 0
assert mobius(6) == 1
assert mobius(30) == -1
print("✓ 练习14通过")

练习15：筛法求欧拉函数¶

题目：编写函数，使用筛法求 1 到 n 的所有欧拉函数值。

要求： - 时间复杂度 O(n log log n) - 返回列表

def euler_phi_sieve(n):
    """
    筛法求欧拉函数

    参数:
        n: 正整数

    返回:
        list: phi[i] = φ(i)
    """
    # 你的代码
    pass

# 测试
phi = euler_phi_sieve(20)
assert phi[1] == 1
assert phi[7] == 6
assert phi[12] == 4
assert phi[100] == 40 if len(phi) > 100 else True
print("✓ 练习15通过")

（三）竞赛练习¶

练习16：第 n 个质数¶

题目：求第 n 个质数。

要求： - n ≤ 10^5 - 使用线性筛法

def nth_prime(n):
    """
    求第 n 个质数

    参数:
        n: 正整数

    返回:
        int: 第 n 个质数
    """
    # 你的代码
    pass

# 测试
assert nth_prime(1) == 2
assert nth_prime(5) == 11
assert nth_prime(10) == 29
assert nth_prime(100) == 541
print("✓ 练习16通过")

练习17：区间质数¶

题目：求区间 [L, R] 内的所有质数。

要求： - R-L ≤ 10^6 - 使用线段筛法

def segmented_sieve(L, R):
    """
    区间筛法

    参数:
        L: 区间下界
        R: 区间上界

    返回:
        list: 区间内的所有质数
    """
    # 你的代码
    pass

# 测试
assert segmented_sieve(100, 150) == [101, 103, 107, 109, 113, 127, 131, 137, 139, 149]
print("✓ 练习17通过")

练习18：大数快速幂¶

题目：计算非常大的数的幂运算结果。

要求： - 处理指数可能很大的情况 - 使用快速幂

def mod_pow_large(a, b, m):
    """
    大数快速幂

    参数:
        a: 底数
        b: 指数（可能很大）
        m: 模数

    返回:
        int: a^b mod m
    """
    # 你的代码
    pass

# 测试
assert mod_pow_large(2, 10**18, 1000) == mod_pow(2, 10**18, 1000)
print("✓ 练习18通过")

练习19：离散对数¶

题目：使用婴儿-巨步算法求解离散对数。

要求： - g^x ≡ y (mod p) - 时间复杂度 O(√p)

def baby_step_giant_step(g, y, p):
    """
    婴儿-巨步算法

    参数:
        g: 原根
        y: 整数
        p: 质数

    返回:
        int: x（如果存在）
             None（如果不存在）
    """
    # 你的代码
    pass

# 测试
assert baby_step_giant_step(2, 3, 13) == 4
assert baby_step_giant_step(5, 2, 23) == 5
print("✓ 练习19通过")

练习20：组合数取模¶

题目：计算 C(n, k) mod p，其中 p 是质数。

要求： - 使用逆元 - 预处理阶乘

def combination_mod(n, k, p):
    """
    计算组合数 C(n, k) mod p

    参数:
        n, k: 非负整数
        p: 质数

    返回:
        int: C(n, k) mod p
    """
    # 你的代码
    pass

# 测试
assert combination_mod(10, 3, 1000000007) == 120
assert combination_mod(100, 50, 1000000007) == 538992043
print("✓ 练习20通过")

练习21：斐波那契数列¶

题目：使用矩阵快速幂计算斐波那契数列的第 n 项。

要求： - 时间复杂度 O(log n) - 支持模运算

def fibonacci(n, mod=None):
    """
    斐波那契数列第 n 项

    参数:
        n: 项数
        mod: 模数（可选）

    返回:
        int: 第 n 项
    """
    # 你的代码
    pass

# 测试
assert fibonacci(10) == 55
assert fibonacci(100, 1000000007) == 687995182
assert fibonacci(0) == 0
assert fibonacci(1) == 1
print("✓ 练习21通过")

练习22：完美数¶

题目：判断一个数是否为完美数。

要求： - 完美数等于其所有真约数之和 - 例如：6 = 1 + 2 + 3

def is_perfect_number(n):
    """
    判断完美数

    参数:
        n: 正整数

    返回:
        bool: 是否为完美数
    """
    # 你的代码
    pass

# 测试
assert is_perfect_number(6) == True
assert is_perfect_number(28) == True
assert is_perfect_number(496) == True
assert is_perfect_number(12) == False
print("✓ 练习22通过")

练习23：亲和数¶

题目：判断两个数是否为亲和数。

要求： - a 的真约数之和等于 b - b 的真约数之和等于 a

def are_amicable_numbers(a, b):
    """
    判断亲和数

    参数:
        a, b: 正整数

    返回:
        bool: 是否为亲和数
    """
    # 你的代码
    pass

# 测试
assert are_amicable_numbers(220, 284) == True
assert are_amicable_numbers(1184, 1210) == True
assert are_amicable_numbers(100, 200) == False
print("✓ 练习23通过")

练习24：求原根¶

题目：判断 g 是否是模 p 的原根。

要求： - p 是奇质数 - g 模 p 的阶为 p-1

def is_primitive_root(g, p):
    """
    判断原根

    参数:
        g: 候选原根
        p: 奇质数

    返回:
        bool: 是否为原根
    """
    # 你的代码
    pass

# 测试
assert is_primitive_root(2, 11) == True
assert is_primitive_root(2, 7) == True
assert is_primitive_root(3, 7) == False
print("✓ 练习24通过")

练习25：米勒-拉宾测试¶

题目：实现米勒-拉宾素性测试。

要求： - 概率性算法 - 可调节测试次数

def miller_rabin(n, k=5):
    """
    米勒-拉宾素性测试

    参数:
        n: 待测试的数
        k: 测试次数

    返回:
        bool: 可能是质数
    """
    # 你的代码
    pass

# 测试
assert miller_rabin(2**61 - 1, k=10) == True  # 梅森质数
assert miller_rabin(2**67 - 1, k=10) == False
print("✓ 练习25通过")

（四）综合项目¶

项目1：数论工具箱¶

目标：实现一个完整的数论工具箱，包含所有基础和进阶功能。

class NumberTheoryToolkit:
    """
    数论工具箱
    """

    def __init__(self):
        pass

    # 在这里实现所有功能
    # - 判断质数
    # - 筛法求质数
    # - GCD 和 LCM
    # - 欧拉函数
    # - 莫比乌斯函数
    # - 模逆元
    # - 线性同余方程
    # - 中国剩余定理
    # - 质因数分解
    # - 快速幂
    # - 离散对数
    # - 组合数取模
    # - 斐波那契数列

    def test_all(self):
        """测试所有功能"""
        print("测试所有功能...")
        # 添加测试代码
        print("✓ 所有测试通过")

# 使用示例
toolkit = NumberTheoryToolkit()
toolkit.test_all()

项目2：RSA 加密系统¶

目标：实现一个完整的 RSA 加密系统，包括： - 密钥生成 - 加密和解密 - 文件加密和解密 - 数字签名

class RSAEncryptionSystem:
    """
    RSA 加密系统
    """

    def __init__(self, bits=1024):
        pass

    # 实现所有功能
    # - 生成密钥对
    # - 加密消息
    # - 解密消息
    # - 加密文件
    # - 解密文件
    # - 数字签名
    # - 验证签名

# 使用示例
rsa = RSAEncryptionSystem(bits=512)
rsa.generate_keys()
# 添加更多功能测试

练习答案¶

提示¶

基础练习：主要考察基本概念的掌握
进阶练习：需要综合运用多个知识点
竞赛练习：需要考虑优化和特殊情况

学习建议¶

按顺序完成：从基础到进阶再到竞赛
独立思考：先自己思考，再参考答案
分析复杂度：每个算法都要分析时间复杂度
优化代码：尝试用不同方法实现，比较效率
总结归纳：做完题目后总结解题思路

章节小结¶

本章提供了从基础到竞赛级别的练习题目：

基础练习：掌握数论的基本概念和算法
进阶练习：综合运用多个知识点
竞赛练习：准备算法竞赛
综合项目：实际应用和系统集成

通过这些练习，你将全面掌握数论的基础知识和算法实现。

恭喜你完成了数论基础教程！

数论是一个博大精深的数学分支，本教程只是入门。继续深入学习吧！

推荐学习资源： - 《数论导引》- G.H. Hardy - 《初等数论》- 潘承洞、潘承彪 - 《具体数学》- Graham, Knuth, Patashnik - 各大 OJ 平台的数论题目