转自：逆元模板总结 - Learn as if you were to live forever - 博客频道 - CSDN.NET
以前一直在用逆元，没想到今天用模板卡了，还是对概念了解的不够。今天在kuangbin神的指导下，稍稍懂了一点。
逆元：
定义 对a∈Zm，存在b∈Zm，使得a+b ≡ 0 (mod m)，则b是a的加法逆元，记b= - a。
定义 对a∈Zm，存在b∈Zm，使得a×b ≡1 (mod m)，则称b为a的乘法逆元。
我们通常所指的是乘法逆元。
然而乘法逆元的应用也需要条件:
对于乘法逆元：在mod
m的操作下（即Zm中），a存在乘法逆元当且仅当a与m互质。不定方程ab+mx=1的任意一组整数解(b,x)，b就是a的乘法逆元。具体计算可以使用扩展欧几里德算法(Extended-GCD)。
kuangbin神给的模板
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
long long extend_gcd(long long a,long long b,long long &x,long long &y)
{
if(a==0&&b==0) return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
long long d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
//*********求逆元素*******************
//ax = 1(mod n)
long long mod_reverse(long long a,long long n)
{
long long x,y;
long long d=extend_gcd(a,n,x,y);
if(d==1) return (x%n+n)%n;
else return -1;
}
以下两种写法都必须要求MOD为素数
1.#define Inv(x) (Pow(x,MOD-2))
由x^(m-1) ≡ 1 (mod m)(费马小定理)
故 x* x^(m-2)≡
1 (mod m),显然x对模m的逆元是x^(m-2)
2.还有一种写法(来源)
可以O(n)时间求逆
int[] inv = new int[MAXN];
inv[1] = 1;
for (int i = 2; i<MAXN; i++)
inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;