拓展欧几里得模板/求逆元模板（java）

拓展欧几里得模板

参考：哈尔滨理工大学ACM培训资料汇编/ACM-ICPC培训资料汇编*

基本原理 ：设 a 和 b 不全为 0，则存在整数 x,y 使得 xa yb=gcd(a,b)=c

对于辗转相除法的最后一项 此时 b=0,则 gcd(a,b)=1a 0b,（这个a,b是经过gcd的最后一项a，b）

因为gcd(a,b)=gcd(b,a%b)

则有x *a y *b=x1 *b y1 * (a%b) 将等式右边变形，

b *x1 (a%b) *y1=b *x1 (a-(a/b) *b) *y1=a *y1 b *(x1-(a/b) *y1)

则，x=y1,y=x1-(a/b) *y1 则可由后向前迭代得到 x,y

解题思路 对于扩展欧几里德定理的题，一般都需要进行一定的推导之后得到一个形式为 xa yb=c 的方程，然后根据 c 确定解是否存在，如果 c 可以被 gcd(a,b)整除，那么方程有 解，否则方程无解。而且所得的解是不唯一的，对于一组解 x0,y0 则其所有解可以表示为 x=x0 b/gcd(a,b)*t,y=y0-a/gcd(a,b)*t,t=0, 1, 2……一般会要求找出 x 或者 y 的最小正整数 解，这个时候需要做一些调整。

总的来说。递归是一来一回的过程，在gcd中，我们只用到了去的过程，求的最大公约数，而在exgcd中，我们发现了在来的过程中，某些数按照一定的规则变化，可以得到我们想要的结果而已。

static long x=0，y=0;
...
static long extgcd(long a,long b)
  {
    if(b==0) {x=1;y=0;return a;}
    long ans=extgcd(b, a%b);
    long team=x;
    x=y;
    y=team-a/b*y;
    return ans;
  }

求逆元：

从拓展欧几里得中知道可以求ax by=c,一般是解决这类问题

当a，b互质时候。c一定等于1.因为gcd（a,b）=1，c必须被gcd整除，那么如果有解一定是1.

那么ax by=1.

求逆元一般形式（求a关于1mod m的逆元）

ax≡1 (mod m). x就是所求的逆元

变形为 ax bm=1

这样就可以运用拓展欧几里得（但是x要大于0处理）

 static long x=0;static long y=0;//全局变量
 ......
 long q=tgcd(a,b);
 // long x1=x;
 if(1%q!=0) {out.println("Not Exist");}
 else {
 while(x<=0){//x*a y*b=1 要求x>0这样并且要求x最小，那么这样操作就相当于 ab-ab操作。刚开始还没明白
 x =b;
 y-=a;
 }
 system.out.println(x);}//
 static long tgcd(long a,long b)
 {
 if(b==0) {x=1;y=0;return a;}
 long ans=tgcd(b,a%b);
 long team=x;
 x=y;
 y=team-a/b*y;
 // System.out.println(x);
 return ans;
 }

还有用小费马可以求逆元，就不介绍了。