等差数列与等比数列求和
算法题里经常遇到"求 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 用的方法。
// 求 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 会丢失余数。
// 正确:先乘后除
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 或先判断奇偶再约分:
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。
// 求 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²
#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 版本:
n = int(input())
print(n * n)
例题:等差数列求和再取模
题目:求 (1 + 2 + ... + n) mod 1000000007,n 最大 10^18。
当 n 很大时,n(n+1) 会溢出 long long,但可以边乘边取模:
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。