問題一覧 > 通常問題

No.1794 Continued Fraction

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 80
作問者 : Kanten4205Kanten4205 / テスター : 👑 KazunKazun
7 ProblemId : 6230 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-22 22:23:44

問題文

正整数 $N,\ M$ が与えられます。次の2つの条件を同時に満たす非負整数列 $A$ を1つ求めてください：

  • $A$ の長さは $60$ 以下。ただし、$A$ の初項を $A_0$ とし、$A=(A_0,A_1, \dots, A_L)$ の長さを $L+1$ とします。
  • $\displaystyle \cfrac{N}{M} = A_0 + \cfrac{1}{A_1 + \cfrac{1}{A_2 + \cfrac{1}{A_3 + \ddots}}}$ を満たす

なお、この問題の制約下では、条件を満たすような $A$ が存在することが証明できます。

入力

$N\ M$

すべてのテストケースは、以下の条件を全て満たします：

  • $1 \leq N, M \leq 10^9$
  • 入力は全て整数である

出力

1 行に、求める数列 $A$ の各要素を空白区切りで出力してください。条件を満たすような $A$ が複数考えられる場合はそのうちの1つを出力してください。

サンプル

サンプル1
入力
36 11
出力
3 3 1 2

$\displaystyle \cfrac{36}{11} = 3 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2}}}$ です。
このとき、$A =(3,\ 3,\ 1,\ 2)$ ですから、これを順に出力すればよいです。また、$A = (3,\ 3,\ 0,\ 0,\ 1,\ 2)$ などを出力しても正解となります。

サンプル2
入力
20 1
出力
20

もとから $\displaystyle \cfrac{N}{M}$ が整数である場合もあります。

サンプル3
入力
10 23
出力
0 2 3 3

$A_0 = 0$ になる場合がありますが、これも必ず出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。