对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然 存在整数对 x,y ,使得 gcd(a,b)=ax+by。
求解 x,y的方法的理解 设 a>b。 1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0; 2,a>b>0 时 设 ax1+ by1= gcd(a,b); bx2+ (a mod b)y2= gcd(b,a mod b); 根据朴素的欧几里德原理有 gcd(a,b) = gcd(b,a mod b); 则:ax1+ by1= bx2+ (a mod b)y2; 即:ax1+ by1= bx2+ (a - [a / b] * b)y2=ay2+ bx2- [a / b] * by2; 也就是ax1+ by1 == ay2+ b(x2- [a / b] *y2); 根据恒等定理得: x1=y2; y1=x2- [a / b] *y2; 这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2. 上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以结束。
以特解 x0 和 y0 表示出整个不定方程的通解:
x = x0 + (b/gcd)*t
y = y0 – (a/gcd)*t
代码:
#include<stdio.h>
int exgcd(int a,int b,int &x,int &y)//引用传值
{
if(b==0)
{
x=1;y=0;
return a;
}
//y=内层的x减掉a/b*y(内层y), x=内层的y
int d=exgcd(b,a%b,y,x);
//内层的y已经赋给了x。
//内层的x已经赋给了y。
y=y-a/b*x;
return d;
}
int main()
{
int a,b,x,y;
while(~scanf("%d%d",&a,&b))
{
int d=exgcd(a,b,x,y);//得到了一组特解
printf("%d*a + %d*b = gcd(a,b) = %d\n",x,y,d);
}
return 0;
}
Python版代码:
def gcd(a,b):
if(b==0):return a,1,0;
d,y,x=gcd(b,a%b)
return d,x,y-a//b*x
a=int(input())
b=int(input())
d,x,y=gcd(a,b)
print("gcd=",d)
print(x,y)
练习题及讲解:http://blog.csdn.net/winter2121/article/details/71123565