逆元与拓展欧几里得算法
一：乘法逆元定义：
若整数 b，p 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(mod p)，则称 x 为 b 的模 p 乘法逆元，记为 b−1(mod p)。 b 存在乘法逆元的充要条件是 b 与模数 p 互质。当模数 p 为质数时，b^(p−2)即为 b 的乘法逆元。
二：快速幂求a%p逆元（p为质数）：
推导：
因为a/b≡a*x(mod p)
对等式两边同时乘b得到：a≡abx(mod p)
同时约去a，得到：1≡b*x(mod p)
所以 1(mod p)=b*x
由费马小定理得到：b^(n-1)≡1(mod p)
同时提出一个b,得到：b*b^(n-2)≡1(mod p)
对比斜体式子得知，x=b^(n-2)
知识补充：
可能有同学好奇费马小定理是啥，这里来补充：
如果我们定义一个p为素数，且定义a和b，a%p≠0，则a^p-1≡1（mod p）。
接下来数学不好者慎入，我们要来证明他了：
首先创造一个集合x，包含所有小于p得数，显然p与集合里的所有数互质。
我们在定义一个集合X，用公式表示是a*x{1,......,p-1}%p=X{a%p,2a%p,......,(p-1)a%p}，
将两个集合里的数分别相乘：(p-1)! % p=a^(p-1)*(p-1)! % p
把所有(p-1)!去掉，得到这个式子：
1(mod p)≡a^(p-1)(mod p)，可以推出式子
a^(p-1)≡1(mod p)。
代码：
有了上述储备，我们可以很轻松的写出代码了。
#include <iostream>
using namespace std;
int quick(long long a,long long b,long long c)
{
long long res=1;
while(b)
{
if(b&1) res=res*a%c; //此二进制位为1
b>>=1; //b右移一位
a=a*a%c; //a扩大一次方
}
return res;
}
int main()
{
int n;
cin>>n;
while(n--)
{
long long a,b;
cin>>a>>b;
if(a%b==0) cout<<"impossible"<<endl;
else cout<<quick(a,b-2,b)<<endl;
}
}三:扩展欧几里得算法求a%p逆元(p不是质数)
裴蜀定理： 若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1. 扩展欧几里得算法：
适用：求解方程 ax+by=gcd(a,b) 的解
易得:b=0时：gcd(a,b)=a
所以x=1,y=0.
b!=0时：由欧几里得算法得到：gcd(a,b)=gcd(b,a%b)
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
得出：x=y′,y=x′−⌊a/b⌋∗y′ 因此可以采用递归，使得某一层中，b=0,即可求出数值。 扩展欧几里得算法对逆元的帮助:
a*x≡1(mod p)
ax=-y*p+1
ax+py=1
代码：
#include <iostream>
using namespace std;
int exgcd(long long a,long long b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;//返回gcd=a
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;//返回gcd=d
}
int main()
{
int n;
cin>>n;
while(n--)
{
long long a,b;
int x,y;
cin>>a>>b;
int d=exgcd(a,b,x,y)==1;
if(d==1) cout<<(x+b)%b<<endl;//保证x>0
else cout<<"impossible"<<endl;
}
}