苍茫大地一剑尽挽破，何处繁华笙歌落。斜倚云端千壶掩寂寞，纵使他人空笑我。

逆元的概念，类似于倒数的性质。

通过上面的引例我们可以粘贴到两个定义：

 

单位元：存在一个集合中的元素【e】，使得给定任意一个集合中的元素a，均有a⊙e=e⊙a=a；逆元：给定任意一个集合中的元素a，存在集合中的另一个元素b，使得a⊙b=b⊙a=e；

那么接下来引入另一个概念啦：

乘法逆元（在维基百科中也叫倒数，当然是 mod p后的,其实就是倒数不是吗？）:

如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。

 

注意：只有a和p互质的时候，a才有关于p的逆元，所以当有多个p和a互质时，所求的a关于p的逆元也是不同的。

a*x ≡ 1 (mod p)  其中x 叫做 a的关于p的逆元，记为：inv(a) = x

所以a * inv(a) ≡ 1 (mod p)

 

举个栗子：

若a*x = 1那么x是a的倒数，x = 1/a

但是a如果不是1，那么x就是小数

那数论中，大部分情况都有求余，所以现在问题变了

a*x ≡ 1 (mod p)

那么x一定等于1/a吗？

不一定的！

所以这时候，我们就把x看成a的倒数，只不过加了一个求余条件，所以x叫做    a关于p的逆元

比如2 * 3 % 5 = 1，那么3就是2关于5的逆元，或者说2和3关于5互为逆元

这里3的效果是不是跟1/2的效果一样？所以才叫数论倒数嘛。

所以上面的除法取余改写为：(a  /  b) % p =  (a * inv(b) ) % p = (a % p * inv(b) % p) % p。

所以我们把错误的除法模运算规则改为了正确的乘法模运算规则了?

 说了那么多，究竟怎么求逆元呢？学长给我们讲了两种方法。

费马小定理

首先再次粘贴一个定理，费马小定理:

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为： 假如p是质数，且gcd(a,p)=1，那么 a(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

 

 

定理内容简单来说就是：a^(p-1) ≡1 (mod p)

求逆元：两边同除以a 得到 a^(p-2) ≡1/a (mod p)

什么(,,• ₃ •,,)，这可是数论，还敢写1/a 应该是a^(p-2) ≡ inv(a) (mod p)

所以inv(a) = a^(p-2) (mod p).

得到公式：inv(a) = a^(p-2) (mod p).

使用条件： p是质数，并且gcd(a,p) = 1.

代码：

typedef long long ll; ll qpow(ll a,ll b,ll p) { ll tmp = 1; a=a%p; while(b) { if(1&b) tmp = tmp*a%p; a = a*a%p; b>>=1; } return tmp%p; } ll inv(ll a,ll p) //费马小定理求逆元 { return qpow(a,p-2,p); }

2.扩展欧几里得

一般用来求解不定方程，求解线性同余方程，求解模的逆元等

内容：若gcd(a,b) = d,那么一定存在x,y使得 ax+by = d.

假设当前要求 gcd(a,b)，并求出了一组 x 和 y 使得 ax+by=GCD(a,b)

已经求出 gcd(b,a%b) 并求出了一组 tx 和 ty 使得 b×tx+(a%b)×ty =GCD(a,b)

那么这两个相邻的状态之间是否存在某种关系呢？

ax+by=GCD=b×tx+(a%b)×ty 

=b×tx+(a−⌊a/b⌋×b)×ty 

=b×tx−⌊a/b⌋×b×ty+a×ty

=b×(tx−⌊a/b⌋×ty)+a×ty

所以 x=ty, y=tx−⌊a/b⌋×ty.

代码：

typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1;y=0;// 当b==0时，此时 x=1,y=0,gcd(a,b)=d=a; return a; } ll tx,ty; ll d= exgcd(b,a%b,tx,ty); x=ty;y=tx-(a/b)*ty; return d; }

那么怎么由扩展欧几里得算法求逆元呢？

很简单~(如果这个词深深的伤害了你，请不要打我?)

使用条件: a,b为正整数，而且gcd(a,b) = 1

证明：

因为a,b 互质，所以一定有 ax+by = 1

两边同时对b 取余

ax%b + by %b = 1%b   ------->   ax%b = 1%b

即 ax ≡ 1 (mod b)

扩展欧几里得中x 就是a关于b的逆元

同理y 就是 b 关于 a的逆元

所以使用完欧几里得算法，我们判断返回值d 是否为1，为1说明 gcd(a,b) = 1

即求得的x就是 a关于b的逆元

void inv(ll a,ll b) { ll x,y; if(exgcd(a,b,x,y) == 1) cout<<"inv(a):"<<x<<endl; else cout<<"不存在逆元"<<endl; }