数论基础----逆元 （数论中的“倒数”）
苍茫大地一剑尽挽破，何处繁华笙歌落。斜倚云端千壶掩寂寞，纵使他人空笑我。
逆元的概念，类似于倒数的性质。
通过上面的引例我们可以粘贴到两个定义：
- 单位元：存在一个集合中的元素【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;
}