Uva 10104 Euclid Problem |x|+|y|最小解 扩展欧几里得
/** url: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1045* stratege: 求ax+by=gcd(a,b), |x|+|y|的和的x,y,的解, 扩展欧几里得，分四种情况考虑* status：1054136710104Euclid ProblemAcceptedC++0.1762012-08-30 05:31:09* Author: johnsondu*/#include <iostream>#include <cstdio>#include <cmath>#include <algorithm>#include <cstring>using namespace std ;#define LL long long void Euclid (LL a, LL b, LL &d, LL &x, LL &y){ if (b == 0) { d = a ; x = 1 ; y = 0 ; return ; } Euclid (b, a%b, d, x, y) ; LL tmp = x ; x = y ; y = tmp - a/b*y ;}LL gcd (LL a, LL b){ return b ? gcd (b, a%b) : a ;}int main (){ #if 0 freopen ("date.txt", "r", stdin) ; #endif LL a, b, d, x, y, i, c ; LL x0, y0 ; LL ax, ay ; LL tx, ty, mins ; while (scanf ("%lld%lld", &a, &b) != EOF) // 扩展欧几里得,求ax+by = Gcd (a,b)的最小正整数解 { //分为4种情况.x的最小正整数,y的最小正整数,x-周期,y-周期 Euclid (a, b, d, x, y) ; //x,y 为 特解, d为a,b 的最大公约数 x0 = (x%b + b) % b ; //x的最小正整数解 （1） y0 = (d-a*x0)/b ; //相应的y值 mins = abs (x0) + abs(y0) ; tx = x0, ty = y0 ; x0-=b ; //x的最小正整数解-x的周期 (2) y0 = (d-a*x0)/b ; //此时相应的y if (abs(x0) + abs(y0) < mins) { mins = abs(x0) + abs(y0) ; tx = x0 ; ty = y0 ; } y0 = (y%a + a) % a ; //y的最小正整数解 （3） x0 = (d-b*y0)/a ; //此时对应的x if (abs(x0) + abs(y0) < mins) { mins = abs(x0) + abs(y0) ; tx = x0 ; ty = y0 ; } y0 -= a ; //y的最小正整数解-y的周期 x0 = (d-b*y0)/a ; //此时对应的x if (abs(x0) + abs(y0) < mins) { mins = abs(x0) + abs(y0) ; tx = x0 ; ty = y0 ; } printf ("%lld %lld %lld\n", tx, ty, d) ; } return 0 ;}