数学问题

1. 扩展欧几里德

线性同余方程（模线性方程）ax=n(mod b)，等价于二元一次不定方程ax+by=n（a,x,b,y,n都是整数）。关于二元一次方程的整数解，有如下简单定理。

(ax+by=n)%b=>(ax=n)%b=>ax=n(mod b)

定理1：若a，b的最大公约数d不能整除n，则方程ax+by=n没有整数解.

例如： 4x+6y=13 gcd(4,6)=2 13/2=6.5

定理2：对于方程ax+by=n，gcd(a,b)=1，如果(x0，y0)是方程的一组整数解，
那么{x=x0+bt; y=y0-at} (t为整数)是方程的全部整数解。

例如： 3x+2y=13 gcd(3,2)=1，如果(x0,y0)=(3,2)是方程的一组解，
那么{x=x0+bt,y=y0-at}(t为整数)是方程的全部解，即xt=3+2t,yt=2-3t是方程的全部解。

解不定方程ax+by=n的步骤如下:

  1. 计算gcd(a,b)，若gcd(a,b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a,b)，得到新的不定方程a'x+b'y=n'，此时gcd(a',b')=1。例如：4x+6y=14=>2x+3y=7,gcd(2,3)=1。
  2. 求出不定方程a'x+b'y=1的一组整数解x0,y0，则n'x0，n'y0是方程a'x+b'y=n'的一组整数解。
  3. 根据定理2，可得方程a'x+b'y=n'的所有整数解为：
    • x=n'x0 + b't
    • y=n'y0 - a't
    • t为整数，这也就是方程ax+by=n的所有整数解。

1.1 求a'x+b'y=1的一组整数解(x0,y0)

那么我们怎么求a'x+b'y=1的一组整数解x0,y0呢？
此时gcd(a',b')=1是我们知道的，gcd为最大公约数，我们还知道求最大公约数用辗转相除方法。

  1. a'x+b'y = gcd(a',b')
  2. a''x' + b''y' = gcd(a'',b'') 辗转第一步即 a'' = b'，b'' = a'%b'
  3. a'''x'' + b'''y'' = gcd(a''',b''') 辗转第二步即 a''' = b''，b''' = a''%b''
  4. ... ... 依此类推，那么什么时候停止呢？
  5. 我们在做辗转相除的时候，在b == 0的时候结束。

在上述式子中即为：a'''x'' +0y'' = gcd(a''',0)

那么我们可以得： a'''x'' = a'''即x'' = 1(单对于这个等式来说，y''可以是任意值， 但是我们需要带回到上一个等式求解，y''任意值)。我们令y''= 0便于计算。

例如：

递推的结果一定是x=1,y=0,那么我们知道了x'' = 1， y''=0，我们怎么才能求出x'？因为x'才是我们要求的。

由ax+by==gcd(a,b)可知bx'+(a%b)y'=gcd(b,a%b),又由gcd(a,b)=gcd(b,a%b)可知

  1. ax+by=bx'+(a%b)y'
  2. = bx'+(a-a/b*b)y'
  3. = bx'+ay'-a/b*by'
  4. = ay'+b(x'-a/by')
  5. 显然x=y'; y=(x'-a/b*y');
  6. 也就是说，上一深度的x等于下一深度的y'，上一深度的y等于下一深度的x'-(a/b)*y'。
  7. 也就实现了x，y的值向上一层传递的问题，进而求出原等式的一组解。

求x0,y0

# include <iostream>
<p class="mume-header " id="include-iostream"></p>

using namespace std;

int x,y;

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

int main(){

	exgcd(15,12);
	
	cout << "x=" << x <<",y=" << y << endl;
	

	return 0;
}

求x,y的通解

# include <iostream>
<p class="mume-header " id="include-iostream-1"></p>

using namespace std;
int x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1;
		y=0;
	}else{
		exgcd(b,a%b);
		int t=x;
		x=y;
		y=t-a/b*x;
	}
}

int gcd(int a,int b){
	int r = a%b;
	while(r){
		a=b;
		b=r;
		r=a%b;
	}
	return b;
}

int main(){
	int a,b,n,a1,b1,n1;
	cin >> a >> b >> n;
	int g = gcd(a,b);
	if(n%g!=0)
		cout << "no integer answer!" << endl;
	else{
		a1=a/g;
		b1=b/g;
		n1=n/g;
		exgcd(a1,b1);

		for(int i=0;i<=10;i++){
			int x2 = n1*x+b1*i;
			int y2 = n1*y-a1*i;
			cout << "t=" << i << ",x=" << x2 << ",y=" << y2 << "=>";
			cout << a << "*" << x2 << "+" << b << "*" << y2 << "=" << a*x2+b*y2 << endl;
		}		
	}


	return 0;
}
≡