HDU - 5912——Fraction

题目：

Mr. Frog recently studied how to add two fractions up, and he came up with an evil idea to trouble you by asking you to calculate the result of the formula below:

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

Input

The first line contains only one integer T, which indicates the number of test cases.

For each test case, the first line contains only one integer n (n≤8).

The second line contains n integers: a1,a2,⋯an(1≤ai≤10).

The third line contains n integers: b1,b2,⋯,bn(1≤bi≤10).

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

1

2

1 1

2 3

Sample Output

Case #1: 1 2

Hint

Here are the details for the first sample:

2/(1+3/1) = 1/2解题思路：这个题主要是模拟公式题，题中给的公式从下往上一个一个推，不过分式不能计算，直接用两个字符去不断存储更新分子分母的值，一直到最后求出分子分母的最大公因数，然后算出最简分式输出。

程序代码：

#include<stdio.h>
#include<string.h>
int a[200],b[200];
int f(int c,int d)//求最大公因数的递归
{
  if(d==0)
    return c;
  else
    return f(d,c%d);
}
int main()
{
  int i,j,k,n,m,cas=1,p,q,t1,t2,t3;
  int N;
  scanf("%d",&N);
  while(N--)
  {
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
      scanf("%d",&b[i]);
    t1=b[n];
    t2=a[n];
    for(i=n;i>=2;i--)//从下往上一直到倒数第二个
    {
      m=t2;
      t2=a[i-1]*t2+t1;
      t1=m*b[i-1];
    }
    p=f(t1,t2); 
    printf("Case #%d: %d %d\n",cas++,t1/p,t2/p);
  }
  return 0;
}