求满足n^n≡0 mod m的最小正整数n的Python代码优化求助

问题描述 #

给定自然数m，编写函数f(m)找出满足nⁿ ≡ 0 mod m（即nⁿ能被m整除）的最小正整数n。示例：

• f(13)=13
• f(420)=210
• f(666)=222
• f(1234567890)=411522630

现有代码问题分析 #

你提供的代码存在以下核心问题：

1. 素因数分解逻辑不严谨：处理大素数时的冗余操作可能导致错误，且未正确记录所有素因子的指数。
2. 核心逻辑错误：通过maxCount和result的比较推导结果的思路不符合问题的数学本质，无法正确满足每个素因子的指数要求。例如当m=8时，代码会返回2，但2²=4无法被8整除，正确结果应为4。
3. 素数遍历错误：遍历primes数组时会包含非素数标记（如0、1），导致后续计算逻辑混乱。

修正思路 #

要解决这个问题，需基于素因数分解和最小公倍数的数学逻辑：

1. 素因数分解：将m分解为m = p₁^k₁ * p₂^k₂ * ... * pₙ^kₙ的形式，其中pᵢ是素数，kᵢ是对应指数。
2. 单个素因子的最小x计算：对每个素因子pᵢ和指数kᵢ，找到最小的xᵢ，使得xᵢ中pᵢ的指数乘以xᵢ大于等于kᵢ（即v_p(xᵢ) * xᵢ ≥ kᵢ，v_p(x)表示x中p的因子次数）。
3. 计算最小公倍数：最终的n是所有xᵢ的最小公倍数，因为n需要同时满足所有素因子的整除要求。

修正后的代码 #

import math

def prime_factorization(m: int) -> dict[int, int]:
    """对m进行素因数分解，返回{素数: 指数}的字典"""
    factors = {}
    # 处理2的情况
    while m % 2 == 0:
        factors[2] = factors.get(2, 0) + 1
        m = m // 2
    # 处理奇数因子
    p = 3
    while p * p <= m:
        while m % p == 0:
            factors[p] = factors.get(p, 0) + 1
            m = m // p
        p += 2
    # 剩余的大素数
    if m > 1:
        factors[m] = 1
    return factors

def min_x_for_p(p: int, c: int) -> int:
    """计算满足v_p(x)*x >= c的最小正整数x"""
    min_x = float('inf')
    t = 1  # x中p的最小次数为1（次数为0时无法满足c>=1的要求）
    while True:
        p_power = p ** t
        # 计算需要的k：k >= c/(t*p_power)，用向上取整
        required_k = (c + t * p_power - 1) // (t * p_power)
        x_candidate = p_power * required_k
        
        # 验证条件（可选，计算逻辑已保证满足）
        k = required_k
        t_k = 0
        while k % p == 0:
            t_k += 1
            k = k // p
        total_t = t + t_k
        if total_t * x_candidate >= c and x_candidate < min_x:
            min_x = x_candidate
        
        # 当p的幂次超过c时，继续增大t只会得到更大的x，停止循环
        if p_power > c:
            if p_power < min_x:
                min_x = p_power
            break
        t += 1
    return min_x

def lcm(a: int, b: int) -> int:
    """计算两个数的最小公倍数"""
    return a * b // math.gcd(a, b)

def f(m: int) -> int:
    if m == 1:
        return 1
    factors = prime_factorization(m)
    current_lcm = 1
    for p, exp in factors.items():
        x_p = min_x_for_p(p, exp)
        current_lcm = lcm(current_lcm, x_p)
    return current_lcm

# 验证示例
print(f(13))          # 输出13
print(f(420))         # 输出210
print(f(666))         # 输出222
print(f(1234567890))  # 输出411522630
print(f(8))           # 输出4

代码说明 #

1. 素因数分解函数：高效分解m为素因子及其指数，覆盖了2、奇数和大素数的情况。
2. 单个素因子最小x计算：通过遍历p的幂次t，计算满足条件的最小候选x，确保找到的x是满足要求的最小值。
3. 最小公倍数计算：将每个素因子对应的最小x取最小公倍数，得到同时满足所有素因子要求的最小n。

内容的提问来源于stack exchange，提问作者Coding Ninja