数学与数论

dongri-chaoxi / 2023-07-29 / 原文

数学知识

平面直角坐标系
二次方程与二次函数
简记符号：$\sum$ $\prod$ $⌊n⌋$ 连加连乘向下取整
等差数列求首项、求末项、求和公式
等比数列首项为 $a$，公比为 $q$，项数为 $n$，求和
- 等比数列：$S=a+aq+aq^2+...+aq^{n-1}$ $①$
- $qS = aq + aq^2 +...+aq^{n}$ $②$
- $② - ①$：$S=a \times \cfrac{1-q^n}{1-q}$
等比数列首项为 $a$，公比为 $q$，有无穷项，求和（若存在）
- $S=\cfrac{a}{1-q}$
计算 $\sum\limits_{i=1}^n \cfrac{n}{i}$：不超过 $n \times log n$
调和级数：$1+\cfrac{1}{2}+\cfrac{1}{3}+\cfrac{1}{4}+\cfrac{1}{5}+...$
- 可以视为 $O(n \times logn)$
- 在做数学、数论（尤其是和倍数有关）的题时对计算时间复杂度有用
快速幂（$a^b$）
- 对 $b$ 进行二进制拆分，同时对 $a$ 进行倍增完成求幂
- 时间复杂度 $O(log b)$
- std::pow 优先保证精度，再保证速度
- 快速幂模板

整除，约数，倍数，最大公约数 $gcd$，最小公倍数 $lcm$
- 辗转相除法求 gcd 模板
- 互质：最大公约数为 1
- $lcm(a,b)=\cfrac{a \times b}{gcd(a,b)}$
质数：如果 $1<k<n$ 的整数 $k$ 都不是 $n$ 的约数
- 质数判断易错点：特判 $1$ 为质数
- 质数判断易错点：循环变量 $i$ 设为 long long
- $\pi(x)$ 表示小于等于 $x$ 的质数个数
- $\pi(x) $ ~ $\cfrac{x}{log_e(x)}$
- ~ 同阶符号（增长速度一致，但是可能会有常数）
埃氏筛质数
- 时间 $O(n log log n)$
- 空间 $O(n)$
欧拉筛质数（每一个合数必须被它的最小质因子标记）
- 时间 $O(n)$
- 空间 $O(n)$
- 核心代码：if (i % pri[j] == 0) break;
唯一分解定理
- 如果 $n \geq 2$ 且是整数，则有唯一分解式$$n=\prod\limits_{i=1}^m {p_i^{k_i}}$$ 其中 $p_1 < p_2 < ... < p_m$ 为质数，$k_i$ 为正整数
模运算与同余定理
- 如果 $a,b$ 为正整数，则 $a$ % $b=a-⌊\cfrac{a}{b}⌋b$
- 同余定理符合加、减、乘、次方，但是不满足除！！
- 同于符号 $≡$
不定方程定理（裴蜀定理）
- $ax+by=gcd(a,b)$
- 求解使用扩展欧几里得算法（特判 $b=0$）
- 例题：P1082 同余方程（求乘法逆元）
  - 原式可转化为：$ax-by=1$
  - 根据裴蜀定理，$ax+by=gcd(a,b)$ 必存在解，原题又保证有解，所以 $gcd(a,b)=1$（$a,b$ 互质）
  - AC记录