Continued Fractions

Let b₀, b₁, b₂,..., b_n be integers with b_k > 0 for k > 0. The continued fraction of order n with coeficients b₁, b₂,..., b_n and the initial term b₀ is defined by the following expression

which can be abbreviated as [b₀;b₁,..., b_n].

An example of a continued fraction of order n = 3 is [2;3, 1, 4]. This is equivalent to

Write a program that determines the expansion of a given rational number as a continued fraction. To ensure uniqueness, make b_n > 1.

Input 

The input consists of an undetermined number of rational numbers. Each rational number is defined by two integers, numerator and denominator.

Output 

For each rational number given in the input, you should output the corresponding continued fraction.

Sample Input 

43 19
1 2

Sample Output 

[2;3,1,4]
[0;2]

---

作法 : 輾轉相除法

#include<stdio.h>
int main() {
    int x, y;
    while(scanf("%d %d", &x, &y) == 2) {
        int A[32], At = 0, tmp, i;
        while(x%y) {
            A[At++] = x/y;
            tmp = x, x = y, y = tmp%y;
        }
        A[At++] = x;
        printf("[%d", A[0]);
        for(i = 1; i < At; i++) {
            if(i == 1)    printf(";");
            else        printf(",");
            printf("%d", A[i]);
        }
        puts("]");
    }
    return 0;
}