数学概念与方法

数论初步

最大公因数算法

辗转相除法，或欧几里得算法（Euclid Algorithm）：

1
2
3
4

int gcd(int a, int b)
{
  return (b == 0) ? a : gcd(b, a%b);
}

值得一提的是，通过 gcd 可以计算出 lcm：

1
2
3
4

int lcm(int a, int b)
{
  return a / gcd(a, b) * b;
}

有一个细节是先除后乘可以避免整数溢出；

素数定理

Eratosthenes 筛法：

1
2
3
4
5
6
7
8

int m = sqrt(n + 0.5);
int c = 0;
memset(vis, 0, sizeof(vis));
for (int i = 2; i <= m; i++) if (!vis[i])
{
  prime[c++] = i;
  for (int j = i*i; j <= n; j += i) vis[j] = 1;
}

素数定义：

• $$\displaystyle \pi(x) \sim \frac{x}{ln(x)}$$，其中 $$\pi(x)$$ 表示不超过 x 的素数数量；

欧几里得扩展算法

欧几里得扩展算法找出以下问题解的一种算法：

• 对于任意的整数 a,b，找出方程的 $$ax + by = gcd(a, b)$$ 的整数解 (x, y)。

找出一组解：

1
2
3
4
5

void gcd(int a, int b, int& d, int& x, int& y)
{
  if (!b) { d = a; x = 1; y = 0; }
  else { gcd(b, a%b, d, y, x); y -= x*(a/b); }
}

通过一组解可以推导出其他的解。

这个算法的一个核心应用就是求逆元，比如 a 关于 b 的逆元 $$a * a^{-1} \equiv 1 \pmod{b}$$，可以先构造方程 $$ax + by = 1$$，方程的解 x 即为 a 关于 b 的逆元。

排列与组合

二项式定理

二项式定理的系数和杨辉三角一样：

• $$\displaystyle (a + b)^n = \sum_{k = 0}^{n} C_n^ka^{n - k}b^k$$

组合数 $$C_n^k$$ 的计算，可以利用数学递推公式 $$\displaystyle C_n^k = \frac{n - k + 1}{k} C_n^{k-1}$$：

1
2
3

memset(C, 0, sizeof(C))
C[0] = 1;
for (int i = 1; i <= n; i++) C[i] = C[i - 1] * (n - i + 1) / i;

欧拉函数

考虑这个问题：

• 给出正整数 n 的唯一分解式 $$n = p_1^{a_1} \cdots p_k^{a_k}$$，求小于 n 且与 n 互素的数字的个数。

上面这个问题的解即称为欧拉函数：

• $$\displaystyle \varphi(n) = \sum_{S \subseteq {p_1, p_2,\cdots, p_k}} (-1)^{|S|} \frac{n}{\prod_{p_i \in S} p_i} = n (1 - \frac{1}{p_1})\cdots(1 - \frac{1}{p_k})$$

在 sage 中，欧拉函数可以直接用 euler_phi 函数计算：

1
2
3

from sage.all import *
print(euler_phi(24), euler_phi(64), euler_phi(187), euler_phi(360))
# (8, 32, 160, 96)

递推

汉诺塔、Fibonacci 数列、Catalan 数。