algo15 数论与组合数学 — exercise.py 练习指南

Download exercise.py

练习目标

通过四个练习巩固数论核心概念：欧拉函数、线性筛扩展、大数快速幂和容斥原理应用。

预备知识

• 欧拉函数的定义和质因子分解公式：$\phi (n)=n\cdot \prod _{p|n}(1-1/p)$
• 线性筛中每个合数只被最小质因子筛一次的原理
• 二进制快速幂的实现（取模版本和大数版本相同）
• 容斥原理的集合交并转换

任务清单

任务1：欧拉函数 euler_phi(n)

• 公式：$\phi (n)=n\times \prod _{p|n}(1-\frac{1}{p})$。
• 实现方法：在质因子分解的过程中计算。对每个质因子 $p$，先除尽 $p$，然后 result -= result // p。

任务2：批量求欧拉函数 euler_phi_range(n)

• 线性筛扩展：当发现素数 $p$ 时，$\phi (p)=p-1$。
• 当筛掉合数 i*p 时：
  • 若 i % p == 0（p 最小质因子）：$\phi (i\cdot p)=\phi (i)\cdot p$
  • 否则：$\phi (i\cdot p)=\phi (i)\cdot (p-1)$

任务3：大数快速幂 fast_pow_big(x, n)

• 与取模版本结构完全相同，只是去掉 % mod。
• Python 自带大整数支持，可以计算非常大的精确值。

任务4：容斥互质计数 count_coprimes_up_to(n, m)

• 步骤1：分解 $m$ 的质因子集合 $P$。
• 步骤2：用容斥原理计算 $1\sim n$ 中至少被 $P$ 中某个质因子整除的数的个数。
• 步骤3：$n$ 减去上一步结果，即为与 $m$ 互质的数的个数。

提示

1. 欧拉函数中注意质因子分解后用 result -= result // p 而非 result *= (1 - 1/p)（整数运算避免浮点）。
2. 批量欧拉函数是线性筛的经典扩展之一。
3. 容斥枚举子集使用位运算 mask 遍历。

# -*- coding: utf-8 -*-
"""
algo15 数论与组合数学 — 练习代码
================================
请完成以下 TODO 任务，巩固数论和组合数学基础。
"""


# ============================================================================
# TODO 1: 欧拉函数 φ(n)
# ============================================================================
def euler_phi(n):
    """
    计算欧拉函数 φ(n)：1~n 中与 n 互质的数的个数。
    公式: φ(n) = n * Π(1 - 1/p)，p 为 n 的所有不同质因子。

    参数:
        n: 正整数
    返回:
        φ(n) 的值
    """
    # TODO: 实现
    # result = n
    # p = 2
    # while p * p <= n:
    #     if n % p == 0:
    #         while n % p == 0:
    #             n //= p
    #         result -= result // p
    #     p += 1
    # if n > 1:
    #     result -= result // n
    # return result
    return 0  # TODO


# ============================================================================
# TODO 2: 批量求 1~n 的欧拉函数（线性筛扩展）
# ============================================================================
def euler_phi_range(n):
    """
    使用线性筛的思想，O(n) 计算 1~n 的所有欧拉函数值。

    参数:
        n: 上限
    返回:
        phi: list, phi[i] = φ(i)
    """
    # TODO: 实现
    pass


# ============================================================================
# TODO 3: 快速幂的大数版本（适用于非取模的大整数幂）
# ============================================================================
def fast_pow_big(x, n):
    """计算 x^n 的精确值（不使用 mod），适用于 x 和 n 不太大但
    结果可能较大的情况（Python 内置大整数支持）。"""
    # TODO: 实现
    # 提示：与取模版本相同，只是去掉 % mod
    return x ** n  # TODO: 替换为快速幂实现


# ============================================================================
# TODO 4: 容斥原理 — 与 m 互质的数的个数
# ============================================================================
def count_coprimes_up_to(n, m):
    """
    计算 1~n 中与 m 互质的数的个数。
    使用容斥原理：总数 - 被 m 的质因子整除的数的个数。

    参数:
        n: 上限
        m: 目标数
    返回:
        1~n 中与 m 互质的数的个数
    """
    # TODO: 1. 分解 m 的质因子
    # TODO: 2. 使用容斥原理统计至少被一个质因子整除的数的个数
    # TODO: 3. n - (至少被一个整除的个数) = 互质的个数
    return 0


# ============================================================================
# 测试代码
# ============================================================================
if __name__ == '__main__':
    print('=' * 50)
    print('algo15 数论与组合数学 — 练习')
    print('=' * 50)

    # 测试 TODO 1: 欧拉函数
    print('\n--- TODO 1: 欧拉函数 φ(n) ---')
    for n in [1, 2, 6, 10, 12, 17]:
        print(f'  φ({n}) = {euler_phi(n)}')

    # 测试 TODO 2: 批量欧拉函数
    print('\n--- TODO 2: 批量 φ(1..n) ---')
    # phi = euler_phi_range(20)
    # for i in range(1, 21):
    #     print(f'  φ({i}) = {phi[i]}')
    print('  (待实现)')

    # 测试 TODO 3: 快速幂大数版
    print('\n--- TODO 3: 大数快速幂 ---')
    print(f'  2^20 = {fast_pow_big(2, 20)} (期望: {2**20})')
    print(f'  3^10 = {fast_pow_big(3, 10)} (期望: {3**10})')

    # 测试 TODO 4: 容斥互质计数
    print('\n--- TODO 4: 1~n 中与 m 互质的个数 ---')
    print(f'  1~30 与 12 互质的数: {count_coprimes_up_to(30, 12)} (期望: 10)')

    print('\n提示: 请补全上方所有 TODO 函数后再运行测试。')