範例程式碼 uva10090

//uva10090
#include <iostream>
#include <cmath>
// 本題背後的數學理論：http://tutorial92.wordpress.com/2012/09/17/uva-10090-marbles-tutorial/

using namespace std;

// 求最大公因數的同時，用輾轉相除法的特性求出 n1 * m1 + n2 * m2 = gcd(n1, n2) 的 m1, m2 值
// (相關知識：https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)
long long int GCD(long long int a, long long int b, long long int *x, long long int *y) {
	// 確保 a 恆大於 b
	if(a < b) {
		long long int buf, *bufP;
		
		buf = a;
		a = b;
		b = buf;
		
		bufP = x;
		x = y;
		y = bufP;
	}
	
	// 輾轉相除法算完的條件
	if(b == 0) {
		*x = 1;
		*y = 0;
		return a;
	}

	long long int gcd, retX, retY;

	// 遞迴法求出最大公因數
	gcd = GCD(b, a % b, &retX, &retY);
	
	// 計算 m1, m2 值
	*x = retY;
	*y = retX - (a / b) * retY;

	return gcd;
}

int main() {
	long long int total, cost1, num1, cost2, num2, box1, box2;

	while(cin >> total) {
		if(total == 0)
			break;

		long long int gcd, bufBox1, bufBox2, myCeil, myFloor, myCost;

		// get input
		cin >> cost1 >> num1 >> cost2 >> num2;

		// get GCD
		gcd = GCD(num1, num2, &bufBox1, &bufBox2);
		
		// N 不整除 gcd 表示不管怎麼湊都湊不出來
		if(total % gcd != 0)
			cout << "failed" << endl;
		else {
			// 由 n1 * m1 + n2 * m2 = gcd(n1, n2) 還原回 n1 * m1 + n2 * m2 = N
			bufBox1 *= (total / gcd);
			bufBox2 *= (total / gcd);
			
			// ceil(-m1 * gcd / n2) <= t <= floor(m2 * gcd / n1) - 詳閱"本題背後的數學理論"
			myCeil = (long long int)ceil(-(double)bufBox1 * gcd / num2);
			myFloor = (long long int)floor((double)bufBox2 * gcd / num1);
			
			// ceil() > floor() 則 t 不存在
			if(myCeil > myFloor)
				cout << "failed" << endl;
			else {
				// cost = c1 * m1 + c2 * m2 = c1 * ( m1 + n2 / gcd * t ) + c2 * ( m2 – n1 / gcd * t)
				//		= c1 * m1 + c2 * m2 + t * (c1 * n2 / gcd – c2 * n1 / gcd)
				// 由於 c1 * m1 + c2 * m2 不影響結果，因此這部分便省略計算 - 算式細節詳閱"本題背後的數學理論"
				myCost = (cost1 * num2 / gcd) - (cost2 * num1 / gcd);
				
				// 最少的 box 數必在極端位置
				if(myCost * myCeil < myCost * myFloor) {
					box1 = bufBox1 + num2 / gcd * myCeil;
					box2 = bufBox2 - num1 / gcd * myCeil;
				}
				else {
					box1 = bufBox1 + num2 / gcd * myFloor;
					box2 = bufBox2 - num1 / gcd * myFloor;
				}
				
				// 輸出最終答案
				cout << box1 << ' ' << box2 << endl;
			}
		}
	}

	return 0;
}