逆元：
如果满足公式，则有a 是 b的逆元同时b也是a的逆元。
逆元的应用：
设c为b在对m取余的意义下的逆元；
在求解公式 (a / b) % m的时候，如果b可能会非常的大，所以会出现爆精度的问题，这个时候就需要将除法转换成乘法来做，即：
(a / b ) % m = (a * c)%m。
逆元的求法：
一、扩展欧几里得求逆元
复杂度：O(logn)（实际就是斐波那契数列）
将公式（b、p已知） a∗b≡1(mod p) 转换为 a∗b+k∗p=1 则有a为b对p取余意义下的逆元，且只有当a与p互质是逆元才存在。
注意：只要存在逆元就可以求，适用于逆元个数不多，但是mod很大的时候。
附一个百度百科的例子加深一下理解：
代码：
/*
Time:2018/8/31
Writer:Sykai
Function:利用扩展欧几里得求逆元
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + ;
const int MOD = 1e9 + ;
typedef long long ll;
typedef pair<int,int> P; //公式a∗b+k∗p=1中a即是a，p即是b
ll exgcd(ll a,ll b,ll& x,ll& y)
{
if(b == )
{
x = ;
y = ;
return a;
}
ll res = exgcd(b, a%b, y, x);
y -= a/b*x;
return res;
}
//公式a∗b+k∗p=1中a即是a，p即是mod
ll getInv(int a,int mod)//求a在mod下的逆元。如果不存在就返回-1
{
ll x,y;
ll res = exgcd(a,mod,x,y);
return res = ? (x%mod + mod)%mod:-;//return res = 1?(x + mod)%mod : -1;
} int main()
{
ll a = ;
printf("%lld\n",getInv(a,MOD));
return ;
}
二、费马小定理求逆元
复杂度：O(logn)
费马小定理： 假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p）。
a*a^(p-2) ≡ 1 (mod p),则有a^(p-2)是a的对p取余时候的逆元
注意：当p是素数的时候一般选用费马小定理来求逆元。
代码：
/*
Time:2018/8/31
Writer:Sykai
Function:利用费马小定理求逆元
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + ;
const int MOD = 1e9 + ;
typedef long long ll;
typedef pair<int,int> P; ll qpow(ll a,ll b)//求a*a^(p-2) ≡ 1 (mod p)中a^(p-2)
{
ll res = ;
while(b)
{
if(b&)
res = res * a % MOD;
a = a * a % MOD;
b >>= ;
}
return res;
} ll getInv(ll a,ll mod)
{
return qpow(a,mod-);
} int main()
{
int a = ;
printf("%lld\n",getInv(a,MOD));
return ;
}
三、递推求逆元
复杂度：O(n)
注意：
1、mod需要是质数，求得是1~N关于mod的逆元。
2、适用于mod不是太大，且被多次调用。
3、程序开始前需要预处理打表。
代码：
/*
Time:2018/8/31
Writer:Sykai
Function:线性求逆元
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + ;
const int MOD = 1e9 + ;
typedef long long ll;
typedef pair<int,int> P;
ll inv[maxn];//数组的大小需要根据实际情况来调整 void getInv()
{
inv[] = ;
for(int i = ; i < maxn; i++)
inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
} int main()
{
getInv();
printf("%lld\n",inv[]);
return ;
}
四、递归求逆元
复杂度：O(logn)
注意：mod需要是素数（中国剩余定理中不太好用）
/*
Time:2018/8/31
Writer:Sykai
Function:递归求逆元
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + ;
const int MOD = 1e9 + ;
typedef long long ll;
typedef pair<int,int> P;
ll inv[maxn];//数组的大小需要根据实际情况来调整 ll getInv(ll x)
{
if(x == ) return ;
return (MOD-MOD/x)*getInv(MOD%x)%MOD;
} int main()
{
printf("%lld\n",getInv());
return ;
}
五、求阶乘的逆元
代码：（不确定怎么用）
/*
Time:2018/8/31
Writer:Sykai
Function:递归求逆元
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6 + ;
const int MOD = 1e9 + ;
typedef long long ll;
typedef pair<int,int> P;
ll inv[maxn];//数组的大小需要根据实际情况来调整
ll fac[maxn+];//阶乘数组
ll qpow(ll a,ll b)
{
ll res = ;
while(b)
{
if(b&)
res = res * a % MOD;
a = a * a % MOD;
b >>= ;
}
return res;
} int main()
{
inv[maxn] = qpow(fac[maxn],MOD-);
for(ll i = maxn-; i>=; i--)
{
inv[i] = (inv[i+]*(i+))%MOD;
}
return ;
}
参考博客：
https://blog.csdn.net/baidu_35643793/article/details/75268911