基本说明
由于数学类方法经常性混合使用（比如组合数+快速幂），因此例题在最后统一给出。
一、最大公约数和最小公倍数（gcd）
1. 定义
没啥好说，大家都懂。最大公约数 gcd(a,b) ，最小公倍数 lcm(a,b) 。
2. 解析
求最大公约一般用辗转相除法，最小公倍数可以由最大公约数导出：
同时注意为了防止a*b溢出，最终我们最小公倍数用下述公式求解：
3. 模板
LL gcd(LL a, LL b) {
return b == 0 ? a : gcd(b, a % b);
}二、扩展欧几里得算法（exgcd）
1. 定义
上面说的求最大公约数的方式实际上叫欧几里得算法，而这里要讲的是它的升级版，不仅可以计算出前面说的最小公约数，还可以求出相应的“不定方程解”.
2. 解析
exgcd可以快速求出下面方程中的x、y、gcd(a,b)：
上面的公式为裴蜀定理，有很多有用的结论：
- 上述式子一定有整数解，通过exgcd可以求出其中一组整数解
- 若要求出其它解，只需要 x+=b/gcd(a,b)，y-=a/gcd(a,b) 即可
- 注意不要漏了除以 gcd(a, b)
- +、-可以互换，相当于从另一个方向找其它解
- 对于ax+by=c，若c不是gcd(a, b)的倍数，则该方程无解
- ......
3. 模板
注意 在求解 ax+by=c 时要特判 a、b等于0 的情况。
LL exgcd(LL a, LL b, ll& x, ll& y) {
if(b == 0) {
y = 0, x = 1;
return a;
}
ll res = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return res;
}三、快速幂算法
1. 定义
一种用来快速求解指数很大的幂运算的算法。
2. 解析
原理是将幂次减半，底数平方，并以此类推直到幂次为0。比如3^10=9^5=(9^4)(9^1)=(81^2)(9^1)=(6561^1)(9^1)，这样原式的答案就是6561*9了。
3. 模板
普通版，注意用long long：
LL fast_pow(LL a, LL b) { // 快速幂算法 LL res = 1; while(b) { if(b & 1) res = res * a; // 指数为奇时分一个出来 b >>= 1; // 指数减半 a = a * a; // 底数平方 } return res; }带mod版，注意用long long：
LL fast_pow_mod(LL a, LL b) { // 快速幂算法 带mod版 LL res = 1; while(b) { if(b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res % mod; }
四、除法求模（逆元）
1. 定义
我们都知道，对于加法、减法、乘法，求模运算都可以提前，即：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p ) % p
(a * b) % p = (a % p * b % p) % p
而除法求模不行，因此对于除法求模我们需要使用一种专门的方法，即转化为乘法求模。
2. 解析
由费马小定理：
转化一下则有：
也就是说，对于除以b取模可以转化为乘以b^(m-2)取模！ 这样就成功将除法取模转化为了乘法取模。但要注意b、m必须互质。好消息是，这里的m一般就是题目给出的mod值，一般题目给出的都是一个很大的质数。
因此我们一般称b^(m-2)为b的 逆元 ，除以b取模相当于乘以b的逆元取模。
而对于b^(m-2)的求法，参见前文的 快速幂算法 即可。
3. 模板
以求组合数的模为例，里面要用到除法（除数为阶乘）求模：
int C(int n, int m) { // n! / (n-m)! / m! => n! * [(n-m)!]^(mod-2) * [m!]^(mod-2)
return fac[n] * inv_fac[n - m] % mod * inv_fac[m] % mod;
}四、指数求模
1. 定义
指数比较大的情况一般用快速幂可以解决，然而....
有时用快速幂还是会超时....这个时候也需要将指数模一模.
2. 解析
由费马小定理：
将k组上式乘到下面这个式子中
得到
上面两个式子说明，可以对指数 模(m-1)，答案不会变化。
3. 结论
在计算指数运算时，要是指数太大，可以 模(m-1)，答案不会变化。m为题目指定的mod。
五、组合数（C(n, m)）
1. 定义
在一些题目中需要用到组合数，甚至通过组合数直接输出结果，因此有必要学习一下组合数的计算方式。
2. 解析
两种方法
方法一：通过动态规划预处理出C[maxn][maxn]数组，预处理用时O(n^2)，查询用时O(1)
一般只要预处理不会超时、空间不会爆 就优先用这个！！方法二：仅预处理出阶乘数fac[maxn]和阶乘数的逆元inv_fac[maxn]，预处理时间O(n*lg(mod))，查询用时稍微慢一点的O(1)
若方法一预处理超时了 或 内存爆了 就用这个。
3. 模板
- 方法一：
void init(ll n) {
C[0][0] = 1;
for(ll i = 1; i <= n; i ++) {
for(ll j = 0; j <= i; j ++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}
}
}- 方法二：
LL fast_pow_mod(LL a, LL b) { // 快速幂
LL res = 1;
while(b) {
if(b & 1) res = res * a % mod;
b >>= 1;
a = a * a % mod;
}
return res % mod;
}
void init(int n) { // 预处理
fac[0] = inv_fac[0] = 1;
for(int i = 1; i <= n; i ++) {
fac[i] = fac[i - 1] * i % mod;
inv_fac[i] = fast_pow_mod(fac[i], mod - 2);
}
}
int C(int n, int m) { // 计算组合数
return fac[n] * inv_fac[n - m] % mod * inv_fac[m] % mod;
}Fin. 例题
Nowcoder 数列统计：https://blog.nowcoder.net/n/44393c613d934015bd7c7a54888535a0
Nowcoder 子序列：（题目链接）https://ac.nowcoder.com/acm/contest/7539/F
Nowcoder 火柴排队：（题目链接）https://ac.nowcoder.com/acm/contest/7329/D
京公网安备 11010502036488号