數論 - UVA 10090 - Marbles

UVA 10090 Marbles


問題

我有 n 個彈珠，我想買一些盒子來裝這些彈珠。盒子有兩種：

第一種盒子：每個盒子要價 c₁ 元，可以裝 n₁ 個彈珠。

第二種盒子：每個盒子要價 c₂ 元，可以裝 n₂ 個彈珠。

我希望用到的每個盒子都裝滿，並且我也希望買盒子的錢花費最少。請你寫一個程式幫我找出我該買這兩種盒子各多少個才好。

* 中文翻譯：Lucky 貓

Input

輸入含有多組測試資料。每組測試資料的第一列有一個正整數 n ，代表彈珠的數目（1 <= n <= 2,000,000,000 ）。第二列有 c₁ 和 n₁ ，第三列有 c₂ 和 n₂ 。在這裡 c₁ 、 n₁ 、 c₂ 、 n₂ 都是小於 2,000,000,000 的正整數。
若 n=0 代表輸入結束。請參考 Sample Input。

Output

對每組測試資料輸出一列，含有2個大於等於0的整數 m₁ ， m₂。代表第一種和第二種盒子該買多少個，使得每個盒子都裝滿彈珠並且花費最少。如果找不到合乎條件的解答，請輸出 "failed"。

Sample Input

43
1 3
2 4
40
5 9
5 12
0

Sample Output

13 1
failed




解法
 github




n1 * x + n2 * y = n


(x, y) 通解為












y=y′∗n/gac(n1,n2)−n1/gcd(n1,n2)∗t