苟蒻发文，若有任何不足、错误的地方欢迎大佬们来斧正~本苟蒻不胜感激（＞人＜；）

一、质因子

  定义： 指能整除给定正整数的质数
  性质： 1没有质因子，每个正整数都能够以唯一的方式表示成它的质因数的乘积
  举例： 360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5，表示成了质因数乘积

时间复杂度： O(logn)，最坏为O($\sqrt{n}$)
算法思想： 从小到大枚举 n 的所有约数，假设枚举较小的那个 p，则 n 中最多只包含一个大于 $\sqrt{n}$ 的质因子，如果枚举结束，n 还大于1，那么说明这就是那个大于 $\sqrt{n}$ 的质因子，由性质的证明如下图。在筛质数的过程中，用的是欧式线性筛法

👉例题1： 点这里
👉例题2： 点这里

/*** 例题1模板 - while循环下就是对应着它的性质*/
#include <bits/stdc++.h>
using namespace std;const int N = 4e5+10;int primes[N];int main(){int n;cin >> n;for(int i = 2; i <= n; i++){int t = i, j = 2;while(t > 1)if(t % j == 0) t /= j, primes[j]++;else j++;}for(int i = 1; i <= 1e4; i++)if(primes[i]) cout << i << " " << primes[i] << endl;return 0;
}

 

二、质数

 定义： 一个正整数无法被除1和它自身以外的自然数整除则为质数
 性质： 任何一个大于1的自然数 n，如果 n 不为质数，那么 n 可以唯一分解成有限个质数的乘积，即 n = $P_1^{{\alpha }_1}\cdot P_2^{{\alpha }_2}\cdot P_3^{{\alpha }_3}\cdot \cdot \cdot P_k^{{\alpha }_k}$，其中$P_1<P_2<\cdot \cdot \cdot <P_k$ 为质数，像${\alpha }_1、{\alpha }_2$之类的为次数

时间复杂度： 欧式筛法为O(n)，埃氏筛法为O(n·logn·logn)
说明： 欧式筛法是线性的，也是我们一般用得较多筛质数的方法。埃氏筛法用的较少，但是它的思路可以用于其他一些题目，思路比较重要

👉例题： 点这里

/*** 欧拉线性筛质数*/#include <bits/stdc++.h>
using namespace std;const int N = 110, M = 1e5+10;int n, cnt;
int nums[N], primes[M];
bool st[M*N];int main(){cin >> n;for(int i = 1; i <= n; i++) cin >> nums[i];for(int i = 2; i <= M; i++){if(!st[i]) primes[cnt++] = i;for(int j = 0; primes[j] <= M/i; j++){	// 从小到大枚举所有质数st[primes[j] * i] = true;			// 只用最小质因子去筛掉合数// 说明primes[j]一定是i的最小质因子，则primes[j]页一定是primes[j]*i的最小质因子// 如果i%primes[j] != 0 的话，说明primes[j]一定小于i的所有质因子if(i % primes[j] == 0) break;}}for(int i = 1; i <= n; i++)if(!st[nums[i]] && nums[i] != 1) cout << nums[i] << " ";return 0;
}

 

三、约数

 定义： 可表示为 N = $P_1^{{\alpha }_1}\cdot P_2^{{\alpha }_2}\cdot P_3^{{\alpha }_3}\cdot \cdot \cdot P_k^{{\alpha }_k}$，P为质数，使得 a 能被 b 整除，则 b 称为 a 的约数
 性质： 点这里参考性质，约数的性质很多都可以用质因数分解表示和解释
 提醒： 约数和倍数其实是一对好基友，当求约数的时间复杂度过大时，不妨从它倍数的角度来考虑解决问题

种类：
 ① 试除法求一个数的所有约数，时间复杂度为 O($\sqrt{n}$)
 ② 求约数个数，时间复杂度为 O($\sqrt{n}$)
 ③ 求约数之和，时间复杂度为 O($\sqrt{n}$)
 ④ 求最大公约数，时间复杂度为 O(logn)

① 试除法求一个数所有约数

#include <bits/stdc++.h>
using namespace std;vector<int> get_diisors(int n){vector<int> res;for(int i = 1; i <= n / i; i++)if(n % i == 0){res.push_back(i);if(i != n / i) res.push_back(n / i);}sort(res.begin(), res.end());return res;
}int main(){int n;while(n--){int x;cin >> x;auto res = get_divisors(x);for(auto t : res) cout << t << ' ';cout << endl;}return 0;
}

 

---

② 求约数个数

约数个数为：$(a_1+1)\cdot (a_2+1)\cdot \cdot \cdot (a_k+1)$

/*** 求约数个数*/#include <bits/stdc++.h>
using namespace std;
typedef long long LL;const int mod = 1e9+7;int main(){int n;cin >> n;unordered_map<int, int> primes;while(n--){int x, j = 2;cin >> x;for(int i = 2; i <= x/i; i++)while(x % i == 0) x /= i, primes[i]++;if(x > 1) primes[x]++;}LL res = 1;for(auto prime : primes)res = res * (prime.second + 1) % mod;cout << res << endl;return 0;
}

Attention： 对于代码中最后判断 x > 1 的举例， 假如 x 为 24，按代码进行下去可知 $x=2^3\times 3$，所以除了 2 还存在 3 这个质因子
👉求约数时时间复杂度过大，从倍数关系来考虑的例题 题解： 点这里
👇 例题题目

👉变种题： 从输入的集合中逐个选取一个数，求剩下的数字有多少个是它的约数
👇解答代码

#include <bits/stdc++.h>
using namespace std;const int N = 1e6+10;int n;
int a[N], cnt[N], res[N];int main(){scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]), cnt[a[i]]++;	// cnt是统计该数字出现了多少次for(int i = 1; i <= N; i++){if(cnt[i] == 0) continue;for(int j = i; j <= N; j+=i)		//j+=i是通过倍数的关系去考虑res[j] += cnt[i];}for(int i = 1; i <= n; i++)printf("%d\n", res[a[i]] - 1);	// -1是不算上它本身return 0;
}

---

③ 求约数和

约数之和为：$(P_1^0+P_1^1+P_1^2+\cdot \cdot \cdot P_2^k)\cdot (P_2^0+P_2^1+P_2^2+\cdot \cdot \cdot P_2^k)\cdot \cdot \cdot (P_k^0+P_k^1+P_k^2+\cdot \cdot \cdot P_k^k)$

/*** 求约数之和*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;const int mod = 1e9+7;int main(){int n;cin >> n;unordered_map<int, int> primes;while(n--){int x, j = 2;cin >> x;for(int i = 2; i <= x/i; i++)while(x % i == 0) x /= i, primes[i]++;if(x > 1) primes[x]++;}LL res = 1;for(auto prime : primes){int p = prime.first, a = prime.second;// 令 t = 1，执行完一次后为 t = p+1// 执行第二次为   t = p^2 + p + 1// 执行 a 次后为  t = p^a + ··· + 1 LL t = 1;while(a--) t = (t * p + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}

👉求约数和（变异）例题：点这里，用区间分块做。
 

---

④ 求最大公约数

<1> gcd辗转相除

我们一般用 gcd辗转相除法(欧几里得算法)，C++可以用STL自带两条下划线的 __gcd(int num1, int num2)，时间复杂度为O(logn)
问题思考：
  a) 基本性质是什么？
  一个数d，如果能实现 d/a、d/b，那么则会有 d/(a+b)、d/(ax+by)
  b) 若是两个数中最大公约数为1，输出的是什么？
  输出1
  c) 若其中有一个数为0或者两个数为0，又该输出什么？
  0与0没有最大公约数，除此之外0与其他数最大公约数为其他数本身

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

 

<2> 扩展欧几里得

定义： 在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 $ax+by=gcd(a,b)$，x 和 y 不唯一

算法证明：
gcd(a, b) = d = ax + by，则有$b\cdot x^{\prime }+(amodb)\cdot y^{\prime }=d$
$amodb=a-[\frac{a}{b}]\cdot b$
$b\cdot x^{\prime }+(a-[\frac{a}{b}]b)\cdot y^{\prime }=d$
移项得$a\cdot y^{\prime }+b(x^{\prime }-[\frac{a}{b}]y^{\prime })\cdot =d$
所以有$\{\begin{array}{c}x=y^{\prime }\\ y=x^{\prime }-[\frac{a}{b}]y^{\prime }\end{array}$

---

当我们在计算exgcd的时候(如下代码)，将x和y翻转一下，便能更好的计算
则有：$a\cdot x^{\prime }+b(y^{\prime }-[\frac{a}{b}]x^{\prime })\cdot =d$
所以有$\{\begin{array}{c}x=x^{\prime }\\ y=y^{\prime }-[\frac{a}{b}]x^{\prime }\end{array}$

👇例题

#include <bits/stdc++.h>
using namespace std;int exgcd(int a, int b, int& x, int& y){if(!b){x = 1, y = 0;//a×1 + 0×0 = areturn a;}//注意这里翻转了y x  有利于后面转换y的时候式子运算int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main(){int n;scanf("%d", &n);while(n--){int a, b, x, y;scanf("%d%d", &a, &b);exgcd(a, b, x, y);printf("%d %d\n", x, y);}return 0;
}

 

<3> 反素数

定义： 对于任何正整数 x ，其约数个数记为 g(x)，对于任意0 < i < x都满足g(i) < g(x)的数称为反素数
性质： 质数的约数个数很少，那么反质数就是约数个数很多。若出现约数个数相等且比 x 小的 $x^{\prime }$，那么取最小 $x^{\prime }$ (因为 x 的约数个数一定大于比它小的 $x^{\prime }$ 的约数个数，所以说明 x 不是反素数)
👉例题： 点这里

/*** 反素数*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int n;
//最小的9个质数
//所有质因数指数总和不超过30,因为2∗3∗5∗7∗9∗11∗13∗17∗19∗23*29 > 2^31-1 > 2*10^9
//所以只考虑到23而不考虑29，并且最小质数的2^30，所以指数最大为30
int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
//maxd最大约数个数，number为这个数字
int maxd, number; //u为p的下标，c是上一个质数的指数，p是当前的数字，s是当前数字的约数个数
void dfs(int u, int c, int p, int s) {if(u == 9) return;if(s > maxd || s == maxd && p < number) {number = p;maxd = s;}//依次选1~c个质数for(int i = 1; i <= c; i++) {if((LL)p * primes[u] > n) break;p *= primes[u];dfs(u + 1, i, p, s * (i + 1));}
}int main()
{cin >> n;//dfs(0, log(n), 1, 1);dfs(0, 30, 1, 1);cout << number;return 0;
}

 

<4> 同余定理

定义：$ax\equiv b(modm)$，(ax - b)能被 m 整除，则称为整数 ax 与 b 对模 m 同余，可化成 $ax=my+b(y\in Z)$。如果是 $ax\equiv 1\cdot (modm)$ 则可求出其 x 的逆

$ax\equiv b(modm)$ 可化成下列式子
$ax=my+b(y\in Z)$
$ax-my=b$
令 $y^{\prime }=y$，则有$ax+m{y}^{\prime }=b$
$gcd(a,m)=d$
只要我们 gcd(a, m) 能整除 b，那么就有解。根据上式即可运用扩展欧几里得算法 $ax+m{y}^{\prime }=d$，只要两边同时扩大就可得到 b，即 $b/d=k$ 算出扩大倍数，将扩展欧几里得的 x 扩大 k 倍，即为我们要求的同余定理中的 x
 
$ax\equiv 1\cdot (modm)$ 可化成下列式子
$ax=my+1;$
$ax-my=1;$
令 $y^{\prime }=y$，则有$ax+m{y}^{\prime }=1$
如果要求满足等式的最小正整数 x (此时x是唯一的)，则不能运用扩展欧几里得算法求解，应该运用欧几里得算法求得
$\{\begin{array}{c}x=x^{\prime }+km\\ y=y^{\prime }-ka\end{array}$
$axmodb=1⟺ax\ne 0⟺x^{\prime }+km\ne 0$
求最小正整数时令 $k=1$ 则 $xmodb=(x^{\prime }modb+b)modb$
👇例题   注意：x不唯一

/*** 同余定理模板*/
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int exgcd(int a, int b, int& x, int& y){if(!b){x = 1, y = 0;//a×1 + 0×0 = areturn a;}//注意这里翻转了y x  有利于后面转换y的时候式子运算int d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}int main(){int n;scanf("%d", &n);while(n--){int a, b, m;scanf("%d%d%d", &a, &b, &m);int x, y, d;d = exgcd(a, m, x, y);if(b % d) puts("impossible");else printf("%lld\n", (LL)x * (b/d)%m);}return 0;
}

 

<5> 费马小定理(快速幂求逆元)

定义： 若 p 为质数，$gcd(a,p)=1$，则 $a^{p-1}\equiv 1(modp)$
可化为 $a\cdot a^{p-2}\equiv 1(modp)$ 用来快速幂求逆元，$a^{p-2}$为$amodp$的逆元，若 a 和 p 不互质（即倍数关系）则无解
证明： 👉点这里

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;inline int qp(int x, int y){int res = 1;for(int i = x; y; y>>=1, i=i*i%p)if(y & 1) res = res*i%p;return res;
}signed main(){int n, a;scanf("%d", &n);while(n--){scanf("%d", &a);int res = qp(a, mod-2);			//要求mod 一定为质数if(a % p) printf("%d\n", res);	//用a % p判断而不用res是因为p为2的时候比较特殊，一定返回1else puts("impossible");		//a 与 p不互质}return 0;
}

 

四、余数

 定义： 余数是整数，指整数除法中被除数未被除尽部分
 应用： 常用于对大数取模、数字拼接、取个位数、余数相加等等
👉例题1： 点这里(余数之和)
  例题1详解：点这里
👉例题2： 点这里(完全平方数)，例题2若看不到题目则看下面图片

 

五、组合数

解法样式：
① DP求解，时间复杂度 $O(n^2)$
② 逆元求解，时间复杂度 $O(n\cdot logn)$
③ 卢卡斯定理，时间复杂度 $O(p\cdot lo{g}_{p}n\cdot logp)$
④ 高精度大数求组合数，时间复杂度
⑤ DFS - 深度搜索树 时间复杂度 $O(lo{g}_{2}n)$

① DP求组合数

思路： 见下图采取闫氏DP分析法

/*** 组合数 - dp求解，时间复杂度：N^2* 10万组   1 <= b <= a <= 2000*/
#include <bits/stdc++.h>
using namespace std;const int N = 2010, mod = 1e9 + 7;int f[N][N];void init(){for(int i = 0; i < N; i++)for(int j = 0; j <= i; j++)if(!j) f[i][j] = 1;else f[i][j] = (f[i-1][j] + f[i-1][j-1]) % mod;
}int main(){init();int n, a, b;scanf("%d", &n);while(n--){scanf("%d%d", &a, &b);printf("%d\n", f[a][b]);}return 0;
}

---

② 逆元求组合数

思路： $C(a,b)=\frac{a!}{(a-b)!\cdot b!}$

/*** 组合数 - 逆元求解，时间复杂度：NlogN* 1万组   1 <= b <= a <= 10^5* C(a, b) = a! / ((a - b)! · b!)*/
#include <bits/stdc++.h>
using namespace std;
#define int long long//注意这里的N不是10010，因为要看a、b的范围存储它的逆的值
const int N = 100010, mod = 1e9 + 7;int n;
int fact[N], infact[N];int qp(int a, int b){int res = 1;for(int i = a; b; b>>=1, i=i*i%mod)if(b & 1) res = res*i%mod;return res;
}signed main(){fact[0] = infact[0] = 1;for(int i = 1; i < N; i++){fact[i] = fact[i-1] * i % mod;infact[i] = infact[i-1] * qp(i, mod-2) % mod;}scanf("%d", &n);while(n--){int a, b;scanf("%d%d", &a, &b);//注意看a、b的大小，因为a > b所以是infact[a-b]printf("%d\n", fact[a] * infact[b] % mod * infact[a-b] % mod);}return 0;
}

---

③ 卢卡斯定理求组合数

思路： $C(a,b)\equiv C(amodp,bmodp)\cdot C(a/p,b/p)$，注意是同余

/*** 组合数 - 卢卡斯定理，时间复杂度：log(p)N·p·logp* 20组     1 <= b <= a <= 10^18      1 <= p <= 10^5* C(a, b) ≡ C(a%p, b%p)· C(a/p, b/p)%p*/
#include <bits/stdc++.h>
using namespace std;
#define int long long		//很重要，不然在逆元求解时会出错int n, p;int qp(int a, int b){int res = 1;for(int i = a; b; b>>=1, i=i*i%p)if(b & 1) res = res*i%p;return res;
}//逆元求解
int C(int a, int b){int res = 1;for(int i = a, j = 1; j <= b; i--,j++){res = res * i % p;res = res * qp(j, p-2) % p;}return res;
}int lucas(int a, int b){if(a < p && b < p) return C(a, b);return C(a%p, b%p) * lucas(a/p, b/p) % p;
}signed main(){scanf("%d", &n);while(n--){int a, b;scanf("%lld%lld%d", &a, &b, &p);printf("%d\n", lucas(a, b));}return 0;
}

---

④ 高精度大数求组合数

思路：
 第一步 - 把范围内的质数筛出来(下面例题的是筛 1 ~ 5000的质数)
 第二步 - 求每个质数的次数
 第三步 - 用高精度乘法把所有质因子乘到一块去

/*** 组合数 - 高精度大数*/
#include <bits/stdc++.h>
using namespace std;const int N = 5010;int primes[N], cnt;
int sum[N];
bool st[N];void getPrime(int n){for(int i = 2; i <= n; i++){if(!st[i]) primes[cnt++] = i;for(int j = 0; primes[j] <= n/i; j++){st[primes[j] * i] = true;if(primes[j] % i == 0) break;}}
}//求 n! 中包含 p 的个数
int get(int n, int p){int res = 0;while(n){res += n /p;n /= p;}return res;
}vector<int> mul(vector<int> a, int b){vector<int> c;int t = 0;for(int i = 0; i < a.size(); i++){t += a[i] * b;c.push_back(t % 10);t /= 10;}while(t){c.push_back(t % 10);		//取出个位t /= 10;}return c;
}int main(){int a, b;scanf("%d%d", &a, &b);getPrime(a);					//线性筛质数for(int i = 0; i < cnt; i++){	//求每个质数的次数int p = primes[i];sum[i] = get(a, p) - get(b, p) - get(a-b, p);}vector<int> res;res.push_back(1);for(int i = 0; i < cnt; i++)			//枚举所有质数for(int j = 0; j < sum[i]; j++)		//枚举质数的次数res = mul(res, primes[i]);for(int i = res.size()-1; i >= 0; i--)printf("%d", res[i]);puts("");return 0;
}

 

六、快速幂

时间复杂度： O(logn)
Attention：在求快速幂的时候不能只用 int，要用long long

/*** 快速幂模板 - 版本一(个人较喜欢用)*/
#define int long long					//不要忘记了这个！！！
const int p = 1e9 + 7;
inline int qp(int x, int y){int res = 1;for(int i = x; y; y>>=1, i=i*i%p)	//此时 i*i 有可能超过int的if(y & 1) res = res*i%p; 		//此时 res*i 也有可能超过intreturn res;
}signed main(){...
}/*** 快速幂模板 - 版本二*/typedef long long LL;					//不要忘记了这个！！！const int p = 1e9+7;int qmi(int a, int b){int res = 1;while(b--){if(b & 1) res = (LL)res*a%p;	//加 LL 和上面模板的道理一样a = (LL)a*a%p;b >>=1;}return res;
}

 
路漫漫其修远兮，吾将上下而求索