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 <stdio.h>

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\n", nu, de);

    return 0;
}

Input

The length of the sequence (0 < n < 10).
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

Add Tag

Discuss