数论
数论概述
数论是研究整数性质的数学分支，是算法竞赛的重要基础。
常见数论问题
- 最大公约数（GCD）
- 最小公倍数（LCM）
- 质数判定
- 质数筛法
- 因数分解
- 欧拉函数
自然数
自然数定义
自然数是指非负整数：0, 1, 2, 3, ...
自然数的性质
- 有序性：可以比较大小
- 封闭性：加法和乘法运算结果仍是自然数
- 离散性：两个相邻自然数之间没有其他自然数
数的奇偶性
奇数和偶数
- 偶数：能被2整除的数，如 0, 2, 4, 6...
- 奇数：不能被2整除的数，如 1, 3, 5, 7...
奇偶性运算规律
奇数 + 奇数 = 偶数
奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数
奇数 × 奇数 = 奇数
奇数 × 偶数 = 偶数
偶数 × 偶数 = 偶数负数
负数定义
小于0的数称为负数，如 -1, -2, -3...
负数运算
a - (-b) = a + b
(-a) × (-b) = a × b
(-a) × b = - (a × b)倍数与约数
约数
若整数a能被整数b整除，则b是a的约数。
倍数
若整数a能被整数b整除，则a是b的倍数。
最大公约数
// 辗转相除法求GCD
int gcd(int a, int b) {
while(b) {
int t = b;
b = a % b;
a = t;
}
return a;
}最小公倍数
lcm(a, b) = a * b / gcd(a, b)模运算与同余
模运算
a mod b 表示a除以b的余数。
(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m同余
若 (a - b) 能被m整除，则称a与b模m同余，记为 a ≡ b (mod m)。
辗转相除法
原理
gcd(a, b) = gcd(b, a mod b)
// 递归实现
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}质数筛法
埃氏筛
vector<bool> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for(int i = 2; i * i <= n; i++) {
if(is_prime[i]) {
for(int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}欧拉筛（线性筛）
vector<int> primes;
vector<bool> is_prime(n+1, true);
is_prime[0] = is_prime[1] = false;
for(int i = 2; i <= n; i++) {
if(is_prime[i]) primes.push_back(i);
for(int p : primes) {
if(i * p > n) break;
is_prime[i * p] = false;
if(i % p == 0) break;
}
}进制
十进制转二进制
// 除2取余法
void dec_to_bin(int n) {
if(n > 0) {
dec_to_bin(n / 2);
cout << n % 2;
}
}二进制转十进制
// 按权展开
int bin_to_dec(string s) {
int res = 0;
for(char c : s) {
res = res * 2 + (c - '0');
}
return res;
}常见进制
- 二进制（base 2）：0, 1
- 八进制（base 8）：0-7
- 十进制（base 10）：0-9
- 十六进制（base 16）：0-9, A-F
排列组合
加法原理
完成一件事有n类方法，第i类有m_i种方法，则总共有 m_1 + m_2 + ... + m_n 种方法。
乘法原理
完成一件事有n个步骤，第i步有m_i种方法，则总共有 m_1 × m_2 × ... × m_n 种方法。
排列
排列定义
从n个元素中选m个元素的排列数：P(n, m) = n! / (n-m)!
// 计算排列数
long long permutation(int n, int m) {
long long res = 1;
for(int i = 0; i < m; i++) {
res *= (n - i);
}
return res;
}组合
组合定义
从n个元素中选m个元素的组合数：C(n, m) = n! / (m!(n-m)!)
// 杨辉三角求组合数
vector<vector<long long>> C(n+1, vector<long long>(n+1));
C[0][0] = 1;
for(int i = 1; i <= n; i++) {
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++) {
C[i][j] = C[i-1][j-1] + C[i-1][j];
}
}函数
函数定义
函数是一种对应关系，每个输入对应唯一的输出。
常见函数
- 一次函数：y = kx + b
- 二次函数：y = ax² + bx + c
- 指数函数：y = a^x
- 对数函数：y = log_a x
几何
平面几何
- 点、线、角
- 三角形：面积、周长、勾股定理
- 四边形：矩形、正方形、平行四边形
- 圆：面积、周长、圆周率
坐标几何
- 距离公式：d = sqrt((x2-x1)² + (y2-y1)²)
- 中点坐标：((x1+x2)/2, (y1+y2)/2)
数列
等差数列
相邻两项的差相等：a_n = a_1 + (n-1)d
求和：S_n = n × (a_1 + a_n) / 2
等比数列
相邻两项的比相等：a_n = a_1 × q^(n-1)
求和：S_n = a_1 × (q^n - 1) / (q - 1)
斐波那契数列
F_n = F_(n-1) + F_(n-2)，F_1 = F_2 = 1