Problem F

Marbles

Input: standard input

Output: standard output

I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types:

Type 1: each box costs c₁ Taka and can hold exactly n₁ marbles

Type 2: each box costs c₂ Taka and can hold exactly n₂ marbles

I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult for me to figure out how to distribute my marbles among the boxes, I seek your help. I want your program to be efficient also.

Input

The input file may contain multiple test cases. Each test case begins with a line containing the integer n (1 <= n <= 2,000,000,000). The second line contains c₁ and n₁, and the third line contains c₂ and n₂. Here, c₁, c₂, n₁ and n₂ are all positive integers having values smaller than 2,000,000,000.

A test case containing a zero for n in the first line terminates the input.

Output

For each test case in the input print a line containing the minimum cost solution (two nonnegative integers m₁ and m₂, where m_i = number of Type i boxes required) if one exists, print "failed" otherwise.

If a solution exists, you may assume that it is unique.

Sample Input

Sample Output

___________________________________________________________________

“The easiest way to count cows in a grazing field is to count how many hooves are there and then divide it by four!”

存在整数 a,b和a,b的最大公约数gcd(a,b)

那么必然存在x,y使得ax+by=gcd(a,b)

在此題要碼 n1 用多一點，不然就 n1 用少一點，因此只要嘗試兩種可能。

設 n1 用 a 盒，n2 用 b 盒

則條件 a * n1 + b * n2 = n, 目標 a * c1 + b * c2 最小。

先從擴充歐幾理德中得到 a' n1 + b' n2 = gcd(n1, n2)

然後將其右邊變成 n，同乘 n/gcd(n1, n2) => a * n1 + b * n2 = n

接著調整 a, b, 試圖將其中一方最小化，

a, b 的參數式 a = a + lcm(n1, n2)/n1 * k, b = b + lcm(n1, n2)/n2 * k

記得 a, b 都要為正數，如果沒辦法則輸出無解。

#include <stdio.h>
#include <algorithm>
using namespace std;
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
int main() {
    long long n, n1, n2, c1, c2;
    while(scanf("%lld", &n) == 1 && n) {
        scanf("%lld %lld %lld %lld", &c1, &n1, &c2, &n2);
        long long a, b, g;
        g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
        if(n%g) {
            puts("failed");
            continue;
        }
        long long k = n/g, k1, k2;
        a *= k, b *= k;// a*n1 + b*n2 = n
        // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0,
        //F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
        k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
        if(a < 0) { // adjust a >= 0
            k = -(a/k1) + (a%k1 != 0);
            a += k*k1, b -= k*k2;
        }
        if(b < 0) { // adjust b >= 0
            k = -(b/k2) + (b%k2 != 0);
            a -= k*k1, b += k*k2;
        }
        if(a < 0 || b < 0) {
            puts("failed");
            continue;
        }
        long long x1, x2, y1, y2;
        // minimize a, maximize b
        k = a/k1;
        a -= k*k1;
        b += k*k2;
        x1 = a, y1 = b;
        // maximize a, minimize b
        k = b/k2;
        a += k*k1;
        b -= k*k2;
        x2 = a, y2 = b;
        if(x1*c1 + y1*c2 < x2*c1 + y2*c2)
            printf("%lld %lld\n", x1, y1);
        else
            printf("%lld %lld\n", x2, y2);
    }
    return 0;
}