如何利用Python高效计算全1多项式的模值？

核心思路 #

你的求和式 ( S = \sum_{i=0}^{n-1} x^i = \frac{x^n - 1}{x-1} )，要计算 ( S \mod m )，关键是在模运算中用逆元替代除法，同时利用Python的pow(x, n, mod)高效完成大幂取模，避免直接计算超大数。

分场景实现 #

由于模运算中除法仅当除数与模数互质时可直接用逆元，我们分两种情况处理：

场景1：x-1与m互质

此时 ( x-1 ) 在模 ( m ) 下存在逆元，直接按以下步骤计算：

1. 用pow(x, n, m)快速计算 ( x^n \mod m )，记为x_n_mod
2. 计算分子并修正负数：(x_n_mod - 1) % m
3. 用pow(x-1, -1, m)获取 ( x-1 ) 的模逆元（Python 3.8+支持负指数求逆元）
4. 结果为分子与逆元的乘积再取模 ( m )

代码示例：

def compute_sum_mod(x, n, m):
    # 题目中x>1，此分支可忽略，仅作鲁棒性补充
    if x == 1:
        return n % m
    x_n_mod = pow(x, n, m)
    numerator = (x_n_mod - 1) % m
    inv = pow(x - 1, -1, m)
    return (numerator * inv) % m

场景2：x-1与m不互质

当 ( \gcd(x-1, m) = d > 1 ) 时，逆元不存在，可通过分解模数处理：

1. 计算最大公约数 ( d = \gcd(x-1, m) )，以及分解后的模数 ( m_1 = m // d )
2. 计算 ( x^n \mod (m_1 * d) )（保证 ( x^n -1 ) 能被 ( d ) 整除），记为x_n_mod
3. 分子分母同时除以 ( d )，得到numerator = (x_n_mod - 1) // d和denominator = (x - 1) // d（此时denominator与m_1互质）
4. 求denominator的模逆元：pow(denominator, -1, m_1)
5. 结果为分子与逆元的乘积再取模 ( m )

通用代码（覆盖所有情况）：

import math

def compute_sum_mod(x, n, m):
    if x == 1:
        return n % m
    d = math.gcd(x - 1, m)
    m1 = m // d
    # 计算x^n mod (m1*d)，确保x^n -1能被d整除
    x_n_mod = pow(x, n, m1 * d)
    numerator = (x_n_mod - 1) // d
    denominator = (x - 1) // d
    inv_denominator = pow(denominator, -1, m1)
    return (numerator * inv_denominator) % m

效率说明 #

• pow(x, n, mod)采用快速幂算法，时间复杂度为 ( O(\log n) )，远快于直接计算大幂再取模
• 所有中间结果都被控制在 ( m1*d ) 范围内（不超过 ( m^2 )，实际运算中数值更小），完全避免内存溢出和低效的大数运算

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