如题目＞▽＜
在基础数论中，逆元是不可或缺的一个概念，它在组合数求取中，由于结果会越来越大，所以题目经常会要求取模，而由于同余式的性质只满足+ - *不满足/，所以我们需要将除法转化为乘法
预备知识
快速幂
代码
1 | //非递归快速幂 |
解释
这里的位运算符，``>>`是右移，表示把二进制数向右移一位，相当于/2；&是按位与，&1可以理解为取出二进制数的最后一位，相当于%2==1
上述是整数的快速幂，但在计算时，如果a的数据类型支持乘法并且满足结合律，那么快速幂的算法都是有效的。矩阵、高精度整数，都可以照搬这个思路。
同余膜运算
假设未知数分别为m、n、p，需要求C(m,n)%p。(0<=m<=n)
求组合数的数学公式：C(m,n) = n! / （m! *(n - m)!）
数学的世界很奇妙，我们知道，模运算的加法，减法，乘法和四则运算类似，即：模运算与基本四则运算有些相似。
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
但对于除法却不成立，即(a / b) % p ≠ (a % p / b % p) % p 。于是我们需要引入逆元的概念
逆元
即建立式子 ax%p=1 ， x的最小正整数解就是 a 的逆元。
求取 (a / b % p) 等同于 求取 (a∗(b的逆元)%p) 。 因此，求模运算的除法问题就转化为就一个数的逆元问题了。
而求取一个数的逆元，有两种方法：
扩展欧几里得算法
该算法（exgcd）可以求取ax + by = gcd(a,b)的整数解x,y。进而可以求取a的逆元x。该算法有三个应用：
- 求解不定方程
- 求解模的逆元
- 求解线性同余方程用扩展欧几里得求取逆元之后(a / b) % p可以换成a * inv(b, p) % p来让除法对 $p$ 取模。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
ll d=exgcd(b,a%b,x,y);
ll k=x;
x=y;
y=k-a/b*y;
return d;
}
ll inv(ll a, ll p) {
ll x, y;
ll gcd = exgcd(a, p, x, y);
return (a%p*x%p) % p;
}
注意：扩展欧几里得定理的使用前提是 gcd(a,p)=1 ，否则逆元不存在费马小定理
在比赛中常见的p为质数，如果a,b<=1e5,p是质数时（常见有1e9+7），我们可以使用费马小定理b^(p-1)%p=1，推出b的逆元是b^(p-2)，使用快速幂求解即可。1
2
3
4
5
6
7
8
9
10
11
12ll qpow(ll a, ll b, ll p) {
ll ans = 1;
while (b) {
if (b & 1) {
ans = ans * a % p;//步步取余
}
a = a * a % p;
b >>= 1;
}
return ans%p;
}
ll inv(ll a, ll p) { return qpow(a, p - 2, p); }组合数
如果n,m很大，能达到1e18,p很小 <= 1e5 ，我们可以利用lucas定理C(n, m) % p = C(n % p, m % p) * lucas(n/p, m/p) % p
1 | // 用于存储阶乘值 |
拓展
这里还有个拓展卢卡斯定理，有兴趣的可以瞧一瞧,戳这里(～￣▽￣)→))￣▽￣)
