将每一个数的所有的倍数都筛去，由于素数只能被1和它本身整除，因此素数不会被筛到，计算量为$n/2+n/3+n/4+...$这个调和级数，复杂度$O(nlogn)$
const int N = 100010;
bool flag[N];
int p[N],tot;
void init(int n) {
for(int i=2;i<=b;++i) {
for(int j=i+i;j<=n;j+=i) {
flag[j] = true;
}
}
for(int i=2;i<=n;++i) {
if(!flag[i]) p[++tot] = i;
}
}
我们注意到朴素版筛法里面 $36$ 会被 $2,3,4,6,9,12,18$ 这 $6$ 个数筛到，相 当于被 $218，312，49，66，94，123，18*2$ 筛到，实际上 \(a?b\) 跟 \(b?a\) 是等价的，于是，我们可以通过枚举小的那个因子，来优化一半的计算量， 相当于 \(i?(i + 1)，i?(i + 2)\) 这样子去筛, 复杂度不变，常数上优化了
void init(int n) {
int up = (int)sqrt(1.0*n) + 1;
for (int i = 2; i <= up; i++) {
for (int j = i * i; j <= n; j += i) {
flag[j] = true;
}
}
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
p[tot++] = i;
}
}
}
那么存在 \(O(n)\) 的筛法，使得每个数只被筛到一次么? 答案是肯定的。 下面这个代码短小精悍，可以做到每一个数只被其最小的素因子筛选到
void init(int n) {
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
p[tot++] = i;
}
for (int j = 0; j < tot; j++) {
if (i * p[j] > n) {
break;
}
flag[i * p[j]] = true; //p[j]是i * p[j]的最小素因子
if (i % p[j] == 0) { // 再往后p[j]就不是i * p[j]的最小素因子了
break;
}
}
}
}
利用辗转相减法求最大公约数, 即 \(gcd(a,b)\)。假设 \(a > b\), 则 \(gcd(a,b) = gcd(a?b,b)\), 不断的利用大的数减去小的数，就能得到最大公约数。
证明：
\(a = k1 ?g\)
\(b = k2 ?g\)
假设 $g $为最大公约数, 那么 \(gcd(k1,k2) = 1\), 设 \(a > b\), 令 \(a = a?b\),
\(a = (k1 ?k2)?g\)
\(b = k2 ?g\)
我们发现 \(a，b\) 的变化为两个互质的系数在不断相减（始终还是互质）， \(g\) 始终是它们的最大公约数，所以当有一个数变成 $0$ 的时候，另一个数就是 最大公约数
while (a != b) {
if(a > b) {
a -= b;
} else {
b -= a;
}
}
我们发现当 \(a\) 一直大于 \(b\) 的时候，就会一直减去 \(b\)，其实就是变成 \(a\%b\)， 于是我们可以利用辗转相除来优化,
while (a && b) {
if (a > b) {
a = a % b; ????
} else {
b = b % a; ????
}
}//循环结束后 max(a,b) 就是答案
int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}
扩展欧几里得的典型应用是解决形如 \(a?x + b?y = c\) 的二元一次方程 的解的存在性问题以及求出特解和通解。
其实我们通过辗转相减就可以观察出来，\(a\),\(b\) 辗转相减的时候相当于 \(a?x+b?y\) 中的 \(x\),\(y\) 在不断变化的过程, 比如 \(a?b\),\(a?2?b\),$3?b?a$，我们 通过前面知道这个过程一定能得到最大公约数, 所以 \(a?x+b?y = gcd(a,b)\) 一定有解，那么是否 \(gcd(a,b)\neq c\) 的时候就无解呢？首先我们知道 \(c\) 是 \(gcd(a,b)\) 的倍数才可能有解，因为左边一定含有因子 \(gcd(a,b)\)，左边等于右 边，那么右边也一定含有 \(gcd(a,b)\)，因此我们可以通过两边同时除以最大公 约数得到一个新的式子
\(k1 ?x + k2 ?y = c/g. gcd(k1,k2) = 1\)
由辗转相减可得：
\(k1?x+k2?y = 1\) 一定有解，所以
\(k1?x+k2?y = c/g\) 一定有解，
所以当 \(c\) 是 \(gcd(a,b)\) 的倍数的时候，方程一定有解
所以我们只需要求解形如
$a?x + b?y = gcd(a,b) $
然后将其扩大$c/gcd(a,b)$倍就可以解出原方程的解了
观察到这个式子的本质其实就是$a$和$b$辗转相减的过程，假设已经求出了
\((a-b) * x_1+ b * y = gcd(a,b)\)
的解$x_1,y_1$，那么变换一下得到$a* x_1 +b * (y_1-x_1) = gcd(a,b)$,我们可以得出
\(x = x_1, y = y_1 - x_1\)
得到了原方程的解，所以我们可以将原问题变成一个规模更小的子问题，然 后根据子问题的答案推出原问题的答案，考虑到这个辗转相减可以用辗转 相除来替代，我们可以将原问题变成求解
\(b ? x_1 + a\%b ? y_1 = gcd(a, b)\)
由
\(a\%b = a - a/b ? b\)
代入得
\(b ? x_1 + (a - a/b ? b) ? y_1 = gcd(a, b)\)
等价于
\(a ? y_1 + b ? (x_1 - a/b ? y_1) = gcd(a, b)\)
得到
\(x = y_1, y = x_1 - a/b ? y_1\)
因此我们只需一直缩小问题规模，直到变成 \(gcd(a, b) ? x + 0 ? y = gcd(a, b)\), 然后得到一组特解 \((1, 0)\)，再将这组特解反推回去，得到一开始的方程的一 组特解。这个过程可以用一个递归函数来实现。
int extgcd(int a, int b, int &x, int &y) {
int d = a;
if(b != 0) {
d = extgcd(b, a % b, x, y);
x -= (a / b) * y;
std::swap(x, y);
} else {
x = 1; y = 0;
}
return d;
}
函数执行完毕后代码里面的 \((x, y)\) 就是 \(a ? x + b ? y = gcd(a, b)\) 的一组 特解, 通解的变化规律就是 \(x\) 和 \(y\) 的值往相反的方向变化，比如 \(x\) 变大一 些，\(y\) 变小一些，使得答案不变，设这个变化的最小单位值为 \(d1\), \(d2\)
\(a ? (x + d_1) + b ? (y - d_2) = gcd(a, b)\)
\(a ? d_1 = b ? d_2\)
两边同除 \(gcd(a, b)\) 令 \(k_1 = a/gcd(a, b)\), \(k_2 = b/gcd(a, b)\)
\(k_1 ? d_1 = k_2 ? d_2\)
这个时候 \(k_1\), \(k_2\) 互质，显然 \(d_1 = k_2\), \(d_2 = k_1\)，可得通解为
\((x + k ? d_1, y - k ? d_2)\)
即
\((x + k ? b/gcd(a, b), y - k ? a/gcd(a, b))\)
我们通过递归函数的实现可以观察到，解的绝对值是跟 a, b 的绝对值 同一个级别的
从$n$个不同元素中，任取$m$（\(m\leq n\),$m$与$n$均为自然数, 下同）个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$个元素的一个排列
从$n$个不同元素中取出$m$(\(m\leq n\))个元素的所有排列的个数，叫做从$n$个不同元素中取$m$个元素的排列数，用符号$A_n^m$ 表示。
计算公式
\(A_n^m= \frac{n!}{(n?m)!}\)
$n$个元素中选$m$(\(m\leq n\)) 个出来，不排序，不在乎顺序就是$C^m_n$。
计算公式
\({C^n_m=\frac{m!}{n!\times (m-n)!}}\)
排列组合的关系为
\(C^m_n×A^m_m=C^m_n×m!=A^n_m\)
建立在杨辉三角上的关系
\(C^n_m = C^{m-n}_m\)
原文：https://www.cnblogs.com/Ax-Dea/p/12036251.html