注: \(\log x = \ln x\)
组合基础
- 加法原理、乘法原理
- 排列数 \(A^m_n = \frac{n!}{(n-m)!}\) : 从 \(1 \sim n\) 选 \(m\) 个数排成一列的方案数
- 组合数 \(C^m_n = \binom{n}{m} = \frac{n!}{(n-m)!m!}\) : 从\(1 \sim n\) 选 \(m\) 个数的方案数。(相对于排列数不考虑顺序)
- \(C^m_n = C^{n-m}_n\)
- \(C^m_n = \frac{n}{m} \times C^{m-1}_{n-1}\)
- \(C^m_n = C^{m-1}_{n-1} + C^m_{n-1}\) (选第 \(n\) 个 + 不选第 \(n\) 个) (杨辉三角)
- \(C^0_n = 1\)
- \(C^1_n = n\)
- \(C^2_n = \frac{(n-1)n}{2}\)
- 二项式定理: \((x + y) ^ n = \sum\limits^n_{k=0}{C^{n-k}_nx^{n-k}y^k}\)
数论基础
- 在 \(1 \sim n\) 大约有 \(\frac{n}{\ln n}\) 个质数，平均每 \(\ln n\) 个数就有 \(1\) 个质数。
- 找第一个大于或小于 \(n\) 的质数，直接从 \(n\) 开始枚举，然后用试除法判断，时间复杂度 \(O(\sqrt n\log n)\)
- 试除法、埃氏筛、线性筛。
- 算数基本定理
- 设 \(n\) 是大于 \(1\) 的整数
- 它的正约数集合是 \(\{\prod\limits^m_{i=1}{p_i^{b_i}}\}, b_i \in [0, c_i] \cap \mathbb{Z}\)
- 它的正约数个数为 \(\prod\limits^n_{i=1}{(c_i+1)}\)
- 它的正约数之和为 \(\prod\limits^m_{i=1}{(\sum\limits^{c_i}_{j=0}p_i^j)}\)
- 一个数 \(n\) 至多只有一个质因数大于 \(\sqrt n\)
- 一个数的因子总是成对出现，除完全平方数外。
- 一个数 \(n\) 的因数个数小于 \(2 \sqrt n\)
- \(1 \sim n\) 每个数的约数个数总和大约有 \(n \log n\) 个。
质数
质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数。
在 \(1 \sim n\) 大约有 \(\frac{n}{\ln n}\) 个质数，平均每 \(\ln n\) 个数就有 \(1\) 个质数。
判定
根据素数的定义，可以写出一下代码，时间复杂度 \(O(\sqrt n)\)
算法一，试除法:
bool is_prime(int x) {
if(x < 2)
return false;
for(int i = 2; i * i <= x; i++)
if(x % i == 0)
return false;
return true;
}
找第一个大于或小于 \(n\) 的质数，直接从 \(n\) 开始枚举，然后用试除法判断，时间复杂度 \(O(\sqrt n\log n)\)
判断 \(1 \sim n\) 之间是否是质数，时间复杂度 \(O(n \sqrt n)\) ，效率太低。
算法二:
bool v[N];
void solve_primes(int n) {
memset(v, 0x00, siaeof(v));
v[0] = v[1] = 1;
for(int i = 2; i <= n; i++)
for(int j = 2; i * j <= n; j++)
v[i * j] = 1;
}
标记每个数的倍数，最后 \(v_x = 0\) 的 \(x\) 是质数。但是和数会标记多次。
时间复杂度 \(O(\sum\limits^n_{i=1}{\frac{n}{i}}) = O(n\sum\limits^n_{i=1}{\frac{1}{i}}) = O(n \log n)\) (调和级数)
算法三， \(\text{Eratosthenes}\) 筛:
bool v[N];
void solve_primes(int n) {
memset(v, 0x00, siaeof(v));
for(int i = 2; i <= n; i++)
if(!v[i])
for(int j = i; i * j <= n; j++)
v[i * j] = 1;
}
标记每个质数的倍数。j 从 i 开始是原来小于 i 的质数会标记 x * i ， 其中 x < i。
但是像 \(24\) 这样的数会被 \(2,3\) 多次标记。
时间复杂度 \(O(n \log{\log{n}})\) ，证明 alfayoung - 通俗易懂的埃氏筛时间复杂度分析
算法四， \(\text{Euler}\) 筛、线性筛:
int v[N];
::std::vector<int> ps;
void solve_primes(int n) {
memset(v, 0x00, sizeof(v));
for(int i = 2; i <= n; i++>)
{
if(!v[i])
ps.push_back(v[i] = i);
for(int j : ps)
if(j > v[i] || i * j > n)
break;
else
v[i * j] = j;
}
}
用一个数的最小质因子来标记它，\(v_x\) 表示 \(x\) 的最小质因子，\(ps\) 是 \(1 \sim n\) 的质数。
每个合数 \(i \times p\) 只会被它的最小质因子 \(p\) 筛一次，时间复杂度 \(O(n)\)
算数基本定理、唯一分解定理
\[\forall n \in [2,+\infty] \cap \mathbb{Z}, \exists p_1, p_2, p_3, ..., p_m \in \mathbb{P}, c_1, c_2, c_3, ..., c_m \in \mathbb{N}_+, \prod\limits^m_{i=1}{p_i^{c_i}}=n. \]任何一个大于 \(1\) 的正整数都能唯一分解为有限个质数的乘积。
设 \(n\) 是大于 \(1\) 的整数，它的正约数集合是 \(\{\prod\limits^m_{i=1}{p_i^{b_i}}\}, b_i \in [0, c_i] \cap \mathbb{Z}\)
它的正约数个数为 \(\prod\limits^n_{i=1}{(c_i+1)}\) 。每个质数选多少个，根据乘法原理乘起来。
它的正约数之和为 \((p_1^0 + p_1^2 + p_1^3 + \cdots + p_1^{c_1}) \times (p_m^0 + p_m^2 + p_m^3 + \cdots + p_m^{c_m}) = \prod\limits^m_{i=1}{(\sum\limits^{c_i}_{j=0}p_i^j)}\) 。每个质数选择若干次和其它的乘起来，变成一个因子，最后若干个因子加起来。
质因数分解
一个数 \(n\) 至多只有一个质因数大于 \(\sqrt n\) 。反证法，对于正整数 \(n\) ，假设有 \(n\) 的两个因子 \(a, b > \sqrt n \land a \neq b\) ，\(a \times b > n\) ，故假设不成立，则命题成立。
int ps[N], c[N], p;
void dec(int x) {
p = 0;
for(int i = 2; i * i <= x; i++)
if(x % i == 0) {
ps[++p] = i, c[p] = 0;
while(x % i == 0)
c[p]++, x /= i;
}
if(x > 1) // x 是质数，或者存在一个质因数大于 sqrt(x)
ps[++p] = x, c[p] = 1;
}
时间复杂度 \(O(\sqrt n)\)
求 \(n\) 的因子集合
一个数的因子总是成对出现，除完全平方数外。
::std::vector<int> div;
void sol(int x) {
for(int i = 1; i * i <= x; i++)
if(x % i == 0) {
v.push_back(i);
if(i * i != x)
v.push_back(x / i);
}
}
时间复杂度 \(O(\sqrt n)\) ，根据时间复杂度可知，一个数 \(n\) 的因数个数小于 \(2 \sqrt n\)
求 \(1 \sim n\) 的因子集合
倍数法、刷表法 : 枚举一个数，看它是那个数的因数。
::std::vector<int> div[N];
void sol(int n) {
for(int i = 1; i <= n; i++)
for(int j = 1; i * j <= n; j++)
div[i * j].push_back(i);
}
时间复杂度 \(O(\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}) = O(n \log n)\) ，根据时间复杂度可知，\(1 \sim n\) 每个数的约数个数总和大约有 \(n \log n\) 个。
标签：frac,limits,组合,数论,质数,基础,sqrt,int,复杂度 From： https://www.cnblogs.com/kuailedetongnian/p/18250728