Description

 

Given two positive integer sequences {a_i} and {b_j} (0 < a_i, b_j < 100), calculate the continued fraction generated by those two sequences.

The continued fraction x is defined as:

For example, if the sequences {a_i} is {2, 7, 3} and {b_j} is {3, 2, 2}, then the answer should be 3/(2+ 7/(2 + 2/(3 + 1))) = 5/8

Note that your answer should be expressed in simplest terms. That is, 2/4 should be represented as 1/2. If the answer is an integer then the denominator should be showed as 1. For example, 3 should be represented as 3/1.

Hint:

You may use the following incomplete code to solve the problem:

#include 

int a[10], b[10];

int gcd(int a, int b)
{
    /* your code here */
}

int main(void)
{
    int i, n;
    int de, nu;
    int tmp, g;
    scanf("%d", &n);

    for (i = 0; i < n; i++) {
        scanf("%d%d", &a[i], &b[i]);
    }

    nu = 1;
    de = 1;
    for (i = 0; i < n; i++) {
        /* your code here */
    }
    printf("%d %d
", nu, de);

    return 0;
}

Input

The length of the sequence (0

a₁ b₁

a₂ b₂

…

a_n b_n

Output

 The output is a pair of numerator and denominator, ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss