[牛客网]A Number Theoretical Problem
题目链接：https://ac.nowcoder.com/acm/problem/207599
这貌似是一道求逆元的模板题，但是。。。
逆元是什么啊！！！扩展欧几里得是什么啊！！！
于是我今天花了一下去看别人的博客，一脸懵逼的进去，一脸懵逼的出来。
其实有很多地方我都搞不明白，但也管不了那么多啦，把我搞明白的讲出来就可以了
首先我们都知道欧几里得算法（也叫辗转相除法）能求出两个数a,b的最大公约数，即gcd（a，b）=gcd（b，a%b）。
复杂度是o（ln n）
代码实现如下：
#include <iostream>
using namespace std;
int gcd(int a,int b);
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d %d\n",a,b);
printf("gcd=%d\n",gcd(a,b));
}
int gcd(int a,int b){
if(b==0) return a;
int ans=gcd(b,a%b);
return ans;
}
再次基础上的扩展欧几里能快速求ax+by=gcd（a，b）一个二元一次方程的一个特解：
当欧几里得算法递归到最后一层，即b==0时，那么gcd=a，这就很容易得到一个特解 x=1,y=0,即a*x+b*y=a*1+b*0=a=gcd
得到特解x=1，y=0，在通过递归的返回，再来一层一层推出原本 ax+by=gck,的一组特解
关于如何推出上一层的特解在这里我们把上一层的解x，y。当前层已知的解为x1，y1
在这里的一个结论是 a%b=a-（a/b）*b （这里的 “/” 指的是整除，例如 5/2=2 , 1/3=0）
由于上一层的gcd（a，b）等于当前层的gcd（b,a%b）
即gcd（b，a%b）=b*x1+（a%b）*y1
=b*x1+（a-(a/b）*b)*y1
=b*x1+ a*y1-(a/b)*b*y1
=a*（y1)+b*(x1-(a/b)*y1)
又因为gcd（a，b）=a*x+b*y，即这两式子相等，通过比较得 x=y1,y=x1-(a/b)*y1。
int gcd(int a,int b,int &x,int &y){
if(b==0){
x=1,y=0; \\ 一组特解
return a;
}
int ans=gcd(b,a%b,x,y);
int t=x; \\由最后一层的一组特解向上推
x=y;
y=t-(a/b)*y;
return ans;
}
如果只能扩展欧几里快速求ax+by=gcd（a，b）一个二元一次方程的一个特解，可能会说：“ 就这？？？”
这里我们就要知道扩展欧几里快速求乘法逆元
然后就是逆元的定义
什么叫乘法逆元？
a*x≡1（mod n） （≡为同余符号，即（a*x）mod n==1 mod n）
这里，我们称 x 是 a 关于 n 的乘法逆元
判断逆元是否存在为gcd（a，n）是否等于1，等于即存在，否则不存在。
我们可以把他写成一个表达式为：a*x+b*y=1（这里设b=n）
于是求逆元就要求这个二元一次方程组，则通过上面所说的扩展欧几里得
但是有无数解，但一般会让你求最小解x0，其实x0mod n就是最小解（这我真搞不明白）
考虑到x0可能是为负数，那我们先对其取模，x0mod n ，但x0还是负数，我们再加上其n，最后再取模。即 x0=（x0%n+n）%n
于是对于牛客上那道求逆元的模板题我们就迎刃而解了
代码如下：
#include <iostream>
typedef long long LL;
using namespace std;
LL exgcd(LL a,LL b,LL &x,LL &y);
int t;
LL y,p;
int main(){
scanf("%d",&t);
while(t--){
scanf("%lld %lld",&y,&p);
LL x=0,k=0;
LL ok=exgcd(y,p,x,k);
if(ok==1) printf("%lld\n",(x%p+p)%p);
else printf("-1\n");
}
}
LL exgcd(LL a,LL b,LL &x,LL &y){
if(b==0){
x=1,y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
LL t=x;
x=y;
y=t-(a/b)*y;
return ans;
}