2016中国大学生程序设计竞赛(ccpc 长春) Fraction【模拟】

Problem Description

As a talent, can you figure out the answer correctly?

Input

Output

For each case, print a line “Case #x: p q”, where x is the case number (starting from 1) and p/q indicates the answer.

You should promise that p/q is irreducible.

Sample Input

Sample Output

Case #1: 1 2

Hint

Here are the details for the first sample:
2/(1+3/1) = 1/2

题意：读入n，输入两行数，第一行是a数组的n个数,第二行是b数组的n个数，按照题目如图所示模拟计算过程，最后结果分数化为最简。

思路：模拟。最后分子分母除以它们最大公约数即最简。

#include<stdio.h>
int a[20],b[20];

int gcd(int a,int b)
{
    int m;
    if( a < b)
        m = a,a=b,b=m;
    while(a%b)
    {
         m = a%b;
        a = b;
        b = m;
    }
    return b;
}

int main()
{
    int T,t,t2=0,i,n,j;
    int x,y;
    scanf("%d",&T);
    while(T --)
    {
        scanf("%d",&n);
        for(i = 1; i <= n; i ++)
            scanf("%d",&a[i]);
        for(i = 1; i <= n; i ++)
            scanf("%d",&b[i]);
        x = a[n-1]*a[n] + b[n];//初始化分子 
        y = a[n];//初始化分母 
        t = x;
        i = n-1;
        j = n-2;
        while(i>0||j>0)//循环模拟计算过程 
        {
            x = y*b[i--] + a[j--]*t;
            y = t;
            t = x; 
        }
        t = gcd(x,y);//求两数最大公约数 
        printf("Case #%d: %d %d
",++t2,x/t,y/t);
    }
    return 0;
}