【学习笔记】exGCD

一、GCD

辗转相除法
$gcd(a,b)=gcd(b,a$ $mod$ $b)$

二、裴蜀定理

裴蜀定理：方程$ax+by=gcd(a,b)$一定存在整数解

三、exGCD

• 作用：求形似ax+by=c的方程的整数解
• 由裴蜀定理，$gcd(a,b)|c$
• 所以只用求$ax+by=gcd(a,b)的解$在把解$\ast \frac{c}{gcd(a,b)}$
• 首先有方程$ax+by=gcd(a,b)$
• 令$A=b,B=a$ $mod$ $b$
  则有$A{x}^{\prime }+B{y}^{\prime }=gcd(A,B)=gcd(a,b)$
• 联立得$b{x}^{\prime }+(a$ $mod$ $b)y^{\prime }=ax+by$
• 又$a$ $mod$ $b$=$a-[\frac{a}{b}]\ast b$
• 代入式子，化简得$a{y}^{\prime }+b(x^{\prime }-[\frac{a}{b}]y^{\prime })=ax+by$
• 则递归可求得解
• 边界：$b=0时,x=1,y=0$

四、例题

NOIp2012同余方程
$ax\equiv 1(mod$ $b)<=>ax+by=1$
用$exgcd$求得$x$一解，若$x<0$，则一直$+b$直到大于0

Code：

#include <bits/stdc++.h>
using namespace std;
int x, y;

void exgcd(int a, int b){
	if (!b){
		x = 1, y = 0; return;
	}
	exgcd(b, a % b);
	int tmp = x;
	x = y, y = tmp - a / b * y;
}

int main(){
	int a, b;
	scanf("%d%d", &a, &b);
	exgcd(a, b);
	while (x < 0) x += b;
	printf("%d\n", x);
	return 0;
}