模板—扩展GCD*2

有必要重新学一下扩展GCD emmmm。

主要是扩展GCD求解线性同余方程$ax≡b (mod p)$。

1.方程有解的充分必要条件：b%gcd（a，p）=0。

　　证明：

$ax-py=b$
由于求解整数解，ax是gcd（a，p）的整数倍，py也是，所以b是gcd（a，p）的整数倍。

2.扩展GCD模板

int exgcd(int a,int b,int &x,int &y)

{

	if(b==0){x=1,y=0;return a;}//注意x，y的赋值。

	int gcd=exgcd(b,a%b,x,y),t=x;

	x=y;y=t-a/b*y;

	return gcd;

}

3.求解线性同余方程：

扩展欧几里得可以求解形如$ax-py=b$的解。

方程可化为$ax≡b (mod p)$,注意b和p的位置。

令t=gcd（a，p）。方程可化为$\frac {a}{t}x-\frac{p}{t}y=\frac{b}{t}$。exgcd求出$\frac {a}{t}x-\frac{p}{t}y=1$的一组特解x，y。$x*=b/t,y*=b/t$即可求出一组解。

而要求最小整数解，可以发现如果x减p，y加a等式仍然成立，所以最小整数解为（x%p+p）%p.

int GCD(int a,int b){return !b?a:GCD(b,a%b);}

int exgcd(int a,int b,int &x,int &y)

{

	if(b==0){x=1,y=0;return a;}

	int gcd=exgcd(b,a%b,x,y),t=x;

	x=y;y=t-a/b*y;

	return gcd;

}

int fcc(int a,int b,int p)

{

	int x,y,t=GCD(a,p);

	if(b%t)return -1;

	int tem=b/t;a/=t,p/=t;

	exgcd(a,p,x,y);

	x*=tem,y*=tem;

	return (x%p+p)%p;

}

巴特西

模板—扩展GCD*2

最新文章

热门文章