扩展欧几里得算法

温故一下,好久没做数论题,都快忘光了。看下扩展欧几里得

/*
1.如果ax+by=c的一组解为(x0,y0),则它的任意整数解都可以写成(x0+kb',y0-ka'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k取任意整数
2.如何求ax+by=c的一组解(x0,y0)?
	设a、b、c为任意整数,ax+by=gcd(a,b)的一组解是(x0,y0),则
	(1)当c是gcd(a,b)的倍数时,ax+by=c的一组解是(x0*(c/gcd(a,b)),y0*(c/gcd(a,b)))
	(2)当c不是gcd(a,b)的倍数时,ax+by=c无整数解
*/
//计算使ax+by=gcd(a,b)的x、y(x、y可以为负)
//a、b中有一个为0时特殊考虑
void exgcd(int a,int b,int& d,int& x,int& y)
{
	if(!b)
	{
		d=a;
		x=1;
		y=0;
	}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=x*(a/b);
	}
	return;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>