台湾菜

扩展欧几里德算法

twcai • acm/icpc

HDOJ 2669
用扩展欧几里德算法求解线性方程,这个内容以前看过,但是不太明白,今天A了题以后感觉有点理解了。数论这方面一定要加强。
该算法是用来求解 a * x + b * y = gcd(a, b) 这个线性方程的,这样的解应该有无数个吧,通过算法求出来的只是其中一个。
若求出来的一组解为X0, Y0, 其他整数解的求法为:
Xi = gcd(a, b) * X0 + b * i;
Yi = gcd(a, b) * Y0 - a * i; (i 为整数)
贴下代码:
#include
using namespace std;

inline void euclid(int a, int b, int &x, int &y)
{
if(b == 0){
x = 1;
y = 0;
return a;
}
else{
int d = euclid(b, a % b, x, y);
int tmp = x;
x = y;
y = tmp - a / b * y;
return d;
}
}

int main()
{
int a, b, x, y, q;

while(scanf("%d %d", &a, &b) != EOF){

q = euclid(a, b, x, y);

if(q == 1){
if(x >= 0){
while(x >= b){
x -= b;
y += a;
}
}
else{
while(x < 0){
x += b;
y -= a;
}
}
printf("%d %dn", x, y);
}
else{
printf("sorryn");
}
}
return 0;
}

/*
97 77
2012 1013
*/

comments powered by Disqus