【扩展欧几里得】POJ 2142 The Balance
KIDx 的解题报告
题目链接：http://poj.org/problem?id=2142
不懂扩展欧几里得请先参照这里：
http://972169909-qq-com.iteye.com/blog/1140914
题意：输入3个数，前2个是砝码的种类，问各要多少个才能称出第三个数出来【同时要使2个答案之和最小】
#include <iostream>#include <cmath>using namespace std;#define inf 0x3fffffff#define LL __int64LL gcd (LL a, LL b){return b ? gcd (b, a%b) : a;}LL Egcd (LL a, LL b, LL &x, LL &y){if (b == 0){x = 1;y = 0;return a;}LL d = Egcd (b, a%b, x, y);LL tp = x;x = y;y = tp - a/b*y;return d;}int main(){LL a, b, n, x, y, vx, vy, d;while (scanf ("%I64d%I64d%I64d", &a, &b, &n), (a||b||n)){d = gcd (a, b);a /= d;b /= d;n /= d;Egcd (a, b, x, y);/**********①令y是最小正整数解**********/vy = y*n;vy = (vy % a + a) % a;//不懂问我vx = (n-b*vy) / a;if (vx < 0)//题目要的是使用砝码的个数，所以要正整数vx = -vx;/**********②令x是最小正整数解**********/x *= n;x = (x % b + b) % b;y = (n-a*x) / b;if (y < 0)//同理y = -y;/**********③使得和最小**********/if (x + y < vx + vy)vx = x, vy = y;printf ("%I64d %I64d\n", vx, vy);}return 0;}