← 返回题目列表

Codeforces · 281/B

B. 最近的分数

中文机器翻译题面 查看原题

给定三个正整数 x、y、n。你的任务是找到最接近分母不超过 n 的分数 $$\frac{x}{y}$$ 的分数。

形式上,您应该找到这样一对整数 a, b (1 ≤ b ≤ n; 0 ≤ a),使得值 $$\left|\frac{x}{y}-\frac{a}{b}\right|$$ 尽可能小。

如果有多个“最接近”的分数,请选择分母最小的一个。如果有多个分母最小的“最接近”分数,请选择分子最小的分数。

输入

单行包含三个整数 x, y, n (1 ≤ x, y, n ≤ 105)。

输出

以“a/b”格式(不带引号)打印所需的分数。

示例

输入 #1

3 7 6

输出 #1

2/5

输入 #2

7 2 4

输出 #2

7/2