1019: 分数化简

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld

Description

 这天老师给小豪出了一道很简单题目放松：输入一个分数，让你求出它们的最简分数。

Input

 第一行包括一个T，表示测试数据的组数。

接下来T行每行包括一个分数。（分子分母均在int范围内）

Output

 对于每个测试样例，输出一行其最简分数。

Sample Input

 

3
2/6
3/1
11/36

 

Sample Output

1/3
3/1
11/36


题目分析：

然而一点点除会爆T

所以用辗转相除法求出最大公因数，然后用分子分母同除。

#include<stdio.h>
#include<string.h>
int min(int x,int y)
{
    int z;
    if(x<y)
        z=x;
    else
        z=y;
    return z;
}
int max(int x,int y)
{
    int z;
    if(x>y)
        z=x;
    else
        z=y;
    return z;
}
int main()
{
	int f,i,j,a,b,n,r,a1,b1,m;
	while(scanf("%d",&n)!=EOF)
	{
		for(j=1;j<=n;j++)
		{
			scanf("%d/%d",&a,&b);
				r=min(a,b);
				a1=a;
				b1=b;
				while(max(a1,b1)%min(a1,b1)!=0)
				{
					r=max(a1,b1)%min(a1,b1);
					if(a1==max(a1,b1))
						a1=r;
					else
						b1=r;
				}
				m=min(a1,b1);
			printf("%d/%d\n",a/m,b/m);
		}
	}
	return 0;
}