中等C++4 分钟1,237 字

等差数列与等比数列求和

算法题里经常遇到"求 1 到 n 的和""求 2 的幂之和"。如果还写一个 O(n) 的循环,在 n 达到 10^9 时就会超时。用数学公式​可以做到 O(1)——这正是 GESP 八级「算法优化」要求的典型场景:用数学知识辅助求解。

等差数列

定义​​:从第二项起,后一项与前一项的差固定为 d(公差)。

a, a+d, a+2d, ..., a+(n-1)d

通项公式​​:

aₙ = a₁ + (n - 1) · d

求和公式(两种形式)​​​:

Sₙ = n·a₁ + n(n-1)d / 2
Sₙ = n(a₁ + aₙ) / 2     ← 首项加末项乘项数除以二

第二个形式更好记,也是高斯小时候算 1+2+...+100 用的方法。

cpp
// 求 1 + 2 + ... + n
long long sum1ToN(long long n) {
    return n * (n + 1) / 2;
}

注意溢出​​:n * (n+1) 在 n 接近 10^9 时会超过 int 范围,必须用 long long。而且要先乘后除——**不能写成 n / 2 * (n + 1)**​​,因为当 n 为奇数时 n / 2 会丢失余数。

cpp
// 正确:先乘后除
long long s = n * (n + 1) / 2;

// 错误:n 为奇数时结果偏小
long long wrong = n / 2 * (n + 1);

如果 n * (n+1) 也超出 long long(n > 3·10^9 左右),可以改用 __int128 或先判断奇偶再约分:

cpp
long long s;
if (n % 2 == 0) s = (n / 2) * (n + 1);
else            s = n * ((n + 1) / 2);

等比数列

定义​​:后一项与前一项的比固定为 q(公比)。

a, aq, aq², ..., aqⁿ⁻¹

通项公式​​:

aₙ = a · qⁿ⁻¹

求和公式​​(q ≠ 1):

Sₙ = a(qⁿ - 1) / (q - 1)

当 q = 1 时,Sₙ = n·a。

cpp
// 求 1 + 2 + 4 + ... + 2^(n-1) = 2^n - 1
long long sumPow2(int n) {
    return (1LL << n) - 1;      // 1 << n 即 2^n
}

这一招在二进制中有多少个 1 的连续前缀和​​、​完全二叉树的节点数​等题目里非常常用:k 层的完全二叉树节点数为 2^k - 1。

例题:用公式代替循环

题目​​:求 1 + 3 + 5 + ... + (2n-1) 的值。n 最大 10^9。

朴素做法​​:循环 n 次,O(n) —— 10^9 次必超时。

公式做法​​:这是首项 1、公差 2、共 n 项的等差数列:

S = n(a₁ + aₙ)/2 = n(1 + 2n - 1)/2 = n²
cpp
#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    cout << n * n << endl;    // 前 n 个奇数之和等于 n 的平方
    return 0;
}

O(1) 解决。这个结论(前 n 个奇数之和 = n²)还可以从几何上理解:每加一个奇数,正方形边长就多 1。

Python 版本:

python
n = int(input())
print(n * n)

例题:等差数列求和再取模

题目​​:求 (1 + 2 + ... + n) mod 1000000007,n 最大 10^18。

当 n 很大时,n(n+1) 会溢出 long long,但可以边乘边取模​​:

cpp
const long long MOD = 1000000007;

long long solve(long long n) {
    long long a = n % MOD;          // n mod MOD
    long long b = (n + 1) % MOD;    // (n+1) mod MOD
    // 除以 2 等价于乘以 2 的逆元 500000004
    return a * b % MOD * 500000004 % MOD;
}

对 1e9+7 取模时,2 的逆元是 (MOD + 1) / 2 = 500000004,因为 2 × 500000004 ≡ 1 (mod 1e9+7)。

常见错误

  • 整数除法丢精度​​:n / 2 * (n + 1) 在 n 为奇数时少算一个 (n+1)/2。
  • 溢出​​:n * (n + 1) 在 n = 10^9 时约 10^18,勉强在 long long 内;n 更大就必须边取模。
  • 混淆公差与项数​​:n 个项,公差 d,末项是 a + (n-1)d,不是 a + n·d。
  • 等比数列 q = 1 除零​​:公式 S = a(qⁿ-1)/(q-1) 在 q = 1 时分母为零,必须特判。

小结

等差数列认准"首项 + 末项 × 项数 / 2",等比数列认准 a(qⁿ-1)/(q-1)。它们能把 O(n) 的循环压成 O(1),是用数学换时间​最直接的例子。写的时候务必先乘后除、注意溢出、特判 q = 1。

同类知识点