10009. Reduce a Fraction

I'm a slow walker, but I never walk backwards.

Task Description

將一個分數化簡到最簡分數。

Input Format

輸入有多組測資,每一組一行兩個整數 $a, \; b$。

  • 80 pt. $0 \le a \le 1000$, $\le b \le 1000$
  • 20 pt. $10^9 \le a \le 2 \times 10^9$, $10^9 \le b \le 2 \times 10^9$

Output Format

對於每組測資輸出一行 x / y

Sample Input

60 80

Sample Output

3 / 4

Hint

AC 者,請寫一份程式只拿 80 分 TLE 試試,體驗一下 時間複雜度 的問題。

多組測資 意即一個測資檔案會有多個測資。

60 80
50 100
0 40

Discussion