H. (网预)The land of LandLord 第十一届北京邮电大学程序设计竞赛 - 热身赛 (1)

时间限制 1000 ms 内存限制 65536 KB

题目描述

Currently the world knows a great number of sensational archaeological discoveries. Data storage devices relating to the period of programming of the XX century were discovered during recent excavations. Decryption of files allowed scientists to prove the hypothesis that ancient programmers were able to make simple arithmetic operations with fractions. Many texts have been deciphered, many mysteries have been solved. However one problem has remained unsolved: a calculation of the smallest positive fraction that, if divided by each of n given fractions , results in an integer number. May be you will manage to solve it...

输入格式

The first line contains an integer n (1≤ n≤ 6) . Each of the following n lines contain two integers ai , bi that are numerator and denominator of irreducible fraction (1≤ ai≤ 103,1≤ bi≤ 109 ) .

 

Multiple cases, end with EOF.

输出格式

Print two positive integers separated by space that are numerator and denominator of the smallest irreducible fraction satisfying the condition of the problem.

输入样例

2 1 2 3 4 2 2 3 4 5

输出样例

3 2 4 1 题意：一个分数除以所给的n个分数，所得的上都是整数，求这个分数的最小值。 思路：此题可以理解为求n个分数的最小公倍数，以所给的最大分数的倍数进行遍历。 #include <bits/stdc++.h> using namespace std; struct num { int a; int b; }num[7]; //求最大公约数 int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } //分数相除 bool divide(int a, int b, int c, int d) { if ((a*d) % (b*c) == 0) return true; return false; } int main() { int n; int maxa, maxb; int a, b; int flag = 1; int temp; while (~scanf("%d", &n)) { maxa = -1; maxb = 1; for (int i = 0; i < n; i++) { scanf("%d %d", &num[i].a, &num[i].b); if ((double)num[i].a / (double)num[i].b > (double)maxa/(double)maxb) { maxa = num[i].a; maxb = num[i].b; } } a = 0; b = maxb; while (1) { a += maxa; //分子（即所给最大分数的倍数） //约分 temp = gcd(a, b); a /= temp; b /= temp; flag = 0; for (int i = 0; i < n; i++) { //判断是否可以整除所给的分数 if (!divide(a, b, num[i].a, num[i].b)) break; flag++; } //flag == n 表示可以整除全部所给的分数 if (flag == n) break; } printf("%d %d\n", a, b); } return 0; }