Uva 10090 Marbles 扩展欧几里得 费用最小
/** url: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1031* stratege: 求n1*x+n2*y=n, x*c1+y*c2的值最小, 扩展欧几里得，分2种情况考虑,x的最小正整数解, y的最小正整数解* status：10090MarblesAcceptedC++0.0202012-08-30 08:10:38* 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 x, LL y){ return y ? Gcd (y, x%y) : x ;}int main (){ LL n, n1, c1, n2, c2, d, x, y, x0, y0, mins, tx, ty, t; while (scanf ("%lld", &n), n) { scanf ("%lld%lld", &c1, &n1) ; scanf ("%lld%lld", &c2, &n2) ; t = Gcd (n1, n2) ; if (n%t) { printf ("failed\n") ; continue ; } n1 /= t, n2 /= t, n /= t ; Euclid (n1, n2, d, x, y) ; mins = -1 ; x *= n ; tx = x0 = ((x%n2)+n2) % n2 ; ty = y0 = (n-x0*n1)/n2 ; if (y0 >= 0) //此时y0的为负数不可取 mins = (x0*c1 + y0*c2) ; y *= n ; y0 = ((y%n1)+n1) % n1 ; x0 = (n-y0*n2)/n1 ; if ((mins > x0*c1 + y0*c2 || mins == -1) && x0 >= 0) //x0为负数不可取 { mins = (x0*c1 + y0*c2) ; tx = x0 ; ty = y0 ; } if (mins == -1) printf ("failed\n") ; else printf ("%lld %lld\n", tx, ty) ; } return 0 ;}