在本节中，我们将探讨等比数列求和这一问题，并学习如何通过高效的算法来解决它。让我们一起来深入分析这个问题，从理解基本概念到掌握优化解法。
问题描述
我们需要计算给定等比数列前 $N$ 项的和。
一个等比数列由以下参数定义：
- A：首项
- R：公比
- N：项数
我们的目标是求出 $S_N = A + A \times R + A \times R^2 + \dots + A \times R^{N-1}$ 的值。
示例分析
为了更好地理解，让我们看几个例子：
示例 1：
输入：A = 2, R = 2, N = 4
数列为：2, 4, 8, 16
输出：30
解释：$2 + 4 + 8 + 16 = 30$
示例 2：
输入：A = 2, R = 3, N = 2
数列为：2, 6
输出：8
解释：$2 + 6 = 8$
解题思路
解决这个问题主要有两种方法：
#### 方法一：迭代法（朴素解法）
最直观的方法是逐项相加。我们可以初始化一个 sum 变量，然后通过循环累加每一项。每一项的值可以通过不断乘以公比 R 来得到。
虽然这种方法逻辑简单，但其时间复杂度为 $O(N)$。当 $N$ 非常大时（例如 $10^9$），这种方法的效率就显得不足了。
#### 方法二：数学公式法（推荐）
为了优化性能，我们可以利用等比数列求和的数学公式。
我们知道，等比数列前 $N$ 项和的公式为：
$$ S_N = A \times \frac{R^N – 1}{R – 1} $$ (当 $R
eq 1$ 时)
如果 $R = 1$，那么数列就是 $A, A, A, \dots$，和直接为 $A \times N$。
使用公式法，我们可以通过快速幂算法在 $O(\log N)$ 的时间复杂度内计算出 $R^N$ 的值，从而极大地提高计算效率，特别是对于 $N$ 很大的情况。
算法实现步骤
- 判断公比：首先检查公比 $R$ 是否为 1。
– 如果 $R == 1$，直接返回 $A \times N$。
- 应用公式：如果 $R
eq 1$，计算 $R^N$。由于结果可能非常大，通常需要对 $10^9 + 7$ 取模（在编程竞赛中常见）。我们需要计算 $(R^N – 1) / (R – 1)$。
- 模运算处理：在模 $10^9 + 7$ 的运算中，除法需要转换为乘以模逆元。
– 我们需要计算 numerator = (pow(R, N) - 1 + MOD) % MOD
– 计算 denominator = (R - 1 + MOD) % MOD
– 计算 denominator_inv = modInverse(denominator, MOD)
– 最终和 sum = (A * numerator % MOD) * denominator_inv % MOD
代码示例
以下是使用数学公式法和快速幂实现的代码：
MOD = 10**9 + 7
def sumOfGP(A, R, N):
# 如果公比为 1，数列所有项都等于 A
if R == 1:
return (A * N) % MOD
# 计算 R^N % MOD
# 使用内置的 pow 函数，它支持快速幂并直接取模
pow_val = pow(R, N, MOD)
# 计算分子：(R^N - 1) % MOD
numerator = (pow_val - 1) % MOD
# 计算分母：(R - 1) % MOD
denominator = (R - 1) % MOD
# 计算分母的模逆元
# 在模数为质数时，可以使用费马小定理：a^(-1) = a^(m-2)
inv_denominator = pow(denominator, MOD - 2, MOD)
# 计算最终结果：A * (分子 / 分母)
total = (A % MOD) * numerator % MOD
total = total * inv_denominator % MOD
return total
# 测试用例
A1, R1, N1 = 2, 2, 4
print(f"输入: A={A1}, R={R1}, N={N1}")
print(f"输出: {sumOfGP(A1, R1, N1)}") # 预期 30
A2, R2, N2 = 2, 3, 2
print(f"输入: A={A2}, R={R2}, N={N2}")
print(f"输出: {sumOfGP(A2, R2, N2)}") # 预期 8
复杂度分析
- 时间复杂度：$O(\log N)$。我们使用了快速幂算法来计算 $R^N$ 以及模逆元。
- 空间复杂度：$O(1)$。我们只使用了常数个额外的变量来存储中间结果。
注意事项
在处理涉及大数和模运算的问题时，我们需要特别注意：
- 溢出问题：在计算过程中（尤其是中间步骤），务必及时进行取模运算，防止数值超出数据类型的表示范围。
- 负数处理：计算 INLINECODEd6346cc7 时可能会得到负数，因此加上 INLINECODEe0b9d364 再进行
% MOD运算是保持结果为正数的标准做法。 - 边界条件：始终检查 $R=1$ 和 $N=0$ 等特殊情况。
通过掌握这种数学解法，我们不仅能解决基本问题，还能轻松应对海量数据的计算挑战。