企业官网建设流程全解析

常见求和公式

1 ~ n 的 k 次方求和

∑(x=1到n) x = 1 + 2 + 3 + … + n

= n(n+1)/2 = 1/2 n² + 1/2 n

∑(x=1到n) x² = 1² + 2² + 3² + … + n²

= n(n+1)(2n+1)/6 = 1/3 n³ + 1/2 n² + 1/6 n

下面是一般形式，前 n 项 k 次方和是一个关于 n 的 k+1 次多项式，其中 a_i 表示求和式的系数：

∑(x=1到n) x^k = 1^k + 2^k + 3^k + … + n^k = ∑(i=0到k+1) a_i n^i

等差数列求和

a + … + b (共n项) = n(a+b)/2

首项和公差的表示法：

- 第 1 项：a

- 公差：d

- 第 n 项：a + (n-1)d

- 求和：na + n(n-1)/2 *d

等比数列求和

简单形式 (q ≥ 0 ∧ q ≠ 1)：

∑(i=0到n) q^i = q^0 + q^1 + … + q^n = (q^(n+1) - 1)/(q - 1)

∑(i=1到n) q^i = q^1 + … + q^n = (q^(n+1) - q)/(q - 1)

特殊情况：

∑(i=0到n) 2^i = 1 + 2 + 4 + 8 + … + 2^n = 2^(n+1) - 1

一般形式 (q ≥ 0 ∧ q ≠ 1)：

- 第 1 项：a

- 公比：q

- 第 n 项：aq^(n-1)

- 求和：a∑(i=0到n-1) q^i = a(q^n - 1)/(q - 1)

推导思路：错位相减法，示例：

令

S = ∑(i=0到n) q^i = q^0 + (q^1 + … + q^n)

qS = ∑(i=1到n+1) q^i = (q^1 + … + q^n) + q^(n+1)

两式相减：

qS - S = q^(n+1) - 1

整理得到结果。

带模幂运算

快速幂分治法，原理：

- 当 n = 0，a^n = 1

- 当 2 | n（偶数），a^n = a^(n/2) × a^(n/2)

- 当 2 ∤ n（奇数），a^n = a × a^(⌊n/2⌋) × a^(⌊n/2⌋)

代码实现（含取模）：

using ll = long long; ll qpow(ll a, ll n){ a %= M; // 参数防爆 if(n == 0) return 1; ll half = qpow(a, n / 2); if(n & 1) return a * half % M * half % M; // 连乘防爆 return half * half % M; }

快速幂倍增法原理：

对 n 进行二进制分解，得到：

n = b0 + b1 + …

其中 bi 的取值为互不相同的 2 的幂

a^n = a^(b0+b1+…) = a^b0 * a^b1 …

用倍增循环计算 a^0 → a^1 → a^2 → a^4 → a^8 → …，同时对 n 进行二进制数位分离，可完成计算，模板：

using ll = long long; ll qpow(ll a, ll n){ ll ret = 1; a %= M; while(n){ if(n & 1) ret = ret * a % M; a = a * a % M; n >>= 1; } return ret; }

当指数很大时，即使用快速幂也效率很低，故需要对指数也进行降幂。当 M 为质数且 a 与 M 互质时，有：

a^n ≡ a^(n mod (M-1)) (mod M)

快速幂降幂

费马小定理：当模为质数，且结果不为模的倍数时，可用费马小定理处理“带模除法”，基本概念：

- 模意义乘法逆元：若 a × b mod M = 1（也做 a × b ≡ 1 (mod M)），则 b 是 a 的乘法逆元，a 也是 b 的乘法逆元。

- 费马小定理：

- a^M mod M = a

- a^(M-1) mod M = 1

- a^(M-2) mod M = b（a × b ≡ 1 (mod M)）

a 的逆元也记作 a^(-1)

利用费马小定理可利用逆元完成除法：

a / b ≡ a × b^(-1) ≡ a × b^(M-2) (mod M)

通常 M 较大，需要快速幂运算

质因子、倍数、因数

唯一分解定理：正整数 a 可唯一分解成若干质数的乘积表示，特别地，对 a = 1，不含任何质数。

通用幂次形式：

a = ∏(i=1到∞) pi^ki

- pi 是第 i 个质数，p1 = 2, p2 = 3, p3 = 5, …

- ki 是 a 含有的第 i 个质数的个数

质因子分解后可完成很多有趣的数论计算。

- 因数个数：τ(n) = ∏(i=1到∞) (ki + 1)

- 因数之和：σ(n) = ∏(i=1到∞) (1 + pi + … + pi^ki) = ∏(i=1到∞) (pi^(ki+1)-1)/(pi-1)

质数密度：π(n) 表示不超过 n 的质数个数，有：

π(n) ≈ n / ln n

利用质因子分解，可以求出多个数的最大公因数（gcd）和最小公倍数（lcm）。

对 n 个整数 a1, …, an，设其质因子分解有：

ai = ∏(j=1到∞) pj^kij

最大公因数取每种质因子的最小值：

gcd(a1,…,an) = ∏(j=1到∞) pj^min(k1j,k2j…knj)

最小公倍数取每种质因子的最大值：

lcm(a1,…,an) = ∏(j=1到∞) pj^max(k1j,k2j…knj)