拓展欧几里得模板/求逆元模板（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;
	}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

求逆元：
从拓展欧几里得中知道可以求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;

 }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

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

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/84196607