天天看点

扩展欧几里德算法 x的最小非负整数解 xy是否有非负整数解

写这个模板的直接原因也是最近在扩展欧几里德上吃了大亏。。

欧几里德算法:

即利用辗转相除法计算a与b的最大公因数gcd

int gcd(int a,int b)
{
	if(!b) return a;
	else return gcd(b,a%b);
}
           

扩展欧几里德算法:

对于同余方程ax=c(mod b)求整数解

即对线性方程ax-by=c求x,y的整数解

我们讨论更一般的情况:

ax+by=c的整数解

扩展欧几里德算法能够求出 ax+by=gcd(a,b) 这样一个方程组x,y和的绝对值的一组整数解,代码如下:

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

若gcd(a,b)整除c,那么只要将ax+by=gcd(a,b)的解(x,y)乘上c/gcd(a,b),就可以得到方程的一组特解:

x0=x*c/gcd(a,b)

y0=y*c/gcd(a,b)

若gcd(a,b)不能整除c,那么方程组就不存在整数解。

那么在方程组有解的情况下,每一个解都能够用它的一组特解来表示:

x=x0 + b / gcd(a,b) * t

y=y0 -  a / gcd(a,b) * t

其中t= 0,1,-1,2,-2,3,-3...证明也非常简单。

那么最常见的两个问题是求最小的非负x,或者求最小的非负(x,y)

对于第一个问题,最小的非负x可以由x0不停地加上b/(a,b)得到

对于第二个问题,最小的非负(x,y)不一定存在,我们需要分情况讨论。

当a<0且b<0时,相当于a>0且b>0时求最大负数解

当a和b中只有一个小于零的时候,非负解一定存在,将(x0,y0)不停地加上(b,a)的绝对值即可

当a和b都大于0时,若x<0,则将x不停加b,y不停减a,若x>0的时候y<0则没有非负解。若x>0时y>0,则根据a和b的大小关系继续加减,确保(x,y)是绝对值和最小的一组非负整数解。

代码如下:

//求最小非负的x 
int exgcd_x(int a,int b,int& x,int& y)
{
	int d=exgcd(a,b,x,y);
	if(x<0)
	{
		b/=d;b>0?b:-b;
		int t=x%b?-x/b:-x/b+1;
		x+=b*t;
	}
	return x; 
}
           

昨天写了求(x,y)的最小非负整数解算法,但是仔细想想发现有问题。

当求ax+by=c的时候,会先求ax+by=gcd(a,b)的一组特解,然后将其乘上c/gcd(a,b),即x*=c/gcd(a,b)。这个时候产生了一个很重要的问题,那就是如果c的范围是10^18,也就是说接近long long的最大范围,那么x*c/gcd(a,b)就有可能爆long long,所以说其实(x,y)的最小非负整数解还是有些细节需要处理的。于是决定根据针对昨天遇到的那道题目来写。

//求ax+by=c是否有非负整数解,保证a,b,c > 0。 a,b<10^9 , c<10^18 
bool exexgcd(long long a,long long b,long long c) 
{
	long long x,y; 
	long long d=exgcd(a,b,x,y);//求扩欧 
	if(c%d) return false;//无解 
	if(x>=0 && y>=0) return true;
	
	if(y<0)//保证x是小于0的那个 
	{
		int temp=a;
		a=b;b=temp;
		temp=x;
		x=y;y=temp;
	}
	
	a/=d;b/=d;c/=d;
	
	//先将x尽量加到接近0 
	long long t=-x/b;
	y-=a*t;
	x+=b*t;
	if(y<0) return false; 
	if(x==0) return true;
	x=-x;//让x取绝对值 
	
	long long right=(y*(c%a)/a)+y*(c/a);
	//表示y在乘上c之后最多能够减多少次a还大于等于0.为了防止爆long long,将c拆开处理了 
	long long left=x*(c%b);
	if(left%b) left=left/b+1;
	else left=left/b;
	left=left-right+x*(c/b); 
	//表示x需要加多少次。同样,为了防止爆long long,不仅把c拆开处理而且还先减去了y能够减的次数right 
	
	//如果x需要加的次数小于等于y能够减的次数,返回true 
	if(left<=0) return true;
	else return false;
}