给出两个正整数a和b(1<=a、b<=1000000)及一个上限L(1<=L<=100)。要求求出他们的简化比例c : d。
规则如下:请你将a比b化简为c比d,要求在c和d均不大于L且a和b互质(两个整数的最大公约数是1)的前提下,c/d ≥ a/b且c/d - a/b(其中:a/b的值小于等于L)的值尽可能小。
输入数据为一行三个整数,分别是a、b、c,两个数之间使用空格隔开。
输出数据为一行两个整数,c和d,两个数之间使用空格隔开。
1498 902 10
5 3
时间限制 | 1 秒 |
内存限制 | 128 MB |