C - Proper Fraction Operation
問題文
正の整数 $A, B, K, N$ が与えられます。
有理数 $\frac{A}{B}$ に対し、以下の操作を $N$ 回行った結果を出力して下さい。
ただし、有理数 $X$ に対する操作を次のように定めます：
-
有理数 $X'$ を次のように定める。
-
$KX < 1$ のとき、$X' = KX$
-
$KX \geq 1$ のとき、$X' = \frac{1}{KX}$
-
-
$X$ を $X'$ に置き換える。
制約
- 入力は全て整数
- $1 \leq A < B \leq 10$
- $1 \leq K \leq 10$
- $1 \leq N \leq 10^{18}$
入力
入力は以下の形式で標準入力から与えられます。
$A$ $B$ $K$ $N$
出力
有理数 $\frac{A}{B}$ に対して $N$ 回操作を行った後の値を、互いに素な正の整数 $C, D$ を用いて $\frac{C}{D}$ と出力してください。
本問題の制約下では、出力すべき値は互いに素な正の整数 $C, D$ を用いて $\frac{C}{D}$ と一意に表すことができます。
出力の際には、以下のように $C, D$ を半角空白区切りで出力してください。
$C$ $D$
1 7 3 2
7 9
$X=\frac{1}{7}$ に対する $1$ 回目の操作は、$KX = 3\cdot\frac{1}{7} \lt 1$ なので、$X' = KX = \frac{3}{7}$ から、$X = \frac{3}{7}$ となります。
$X = \frac{3}{7}$ に対する $2$ 回目の操作は、$KX = 3\cdot\frac{3}{7} \ge 1$ なので、$X' = \frac{1}{KX} = \frac{7}{9}$ から、$X = \frac{7}{9}$ となります。
出力すべき値は $X$ を互いに素な正の整数 $C,D$ を用いて $\frac{C}{D} = \frac{7}{9}$ と一意に表せるため、7 9 と出力してください。
3 4 2 1
2 3
例えば 4 6 と出力すると WA となるので注意してください。