問題一覧 > 通常問題

No.1794 Continued Fraction

レベル : / AI推定難易度 : 189 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 87
作問者 : Kanten4205 / テスター : 👑 Kazun
お気に入りにしたユーザー ProblemId : 6230 / 自分の提出
問題文最終更新日: 2021-12-22 22:23:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

You are given positive integers $N,\ M$. Find one sequence $A$ of non-negative integers that satisfies both of the following two conditions:

  • The length of $A$ is at most $60$. Here, the first term of $A$ is $A_0$, and the length of $A=(A_0,A_1, \dots, A_L)$ is $L+1$.
  • It satisfies $\displaystyle \cfrac{N}{M} = A_0 + \cfrac{1}{A_1 + \cfrac{1}{A_2 + \cfrac{1}{A_3 + \ddots}}}$.

It can be proved that, under the constraints of this problem, an $A$ satisfying the conditions exists.

Input

$N\ M$

All test cases satisfy all of the following conditions:

  • $1 \leq N, M \leq 10^9$
  • All inputs are integers.

Output

Output the elements of the sequence $A$ on one line, separated by spaces. If there are multiple possible $A$ satisfying the conditions, output any one of them.

Sample

Sample 1
Input
36 11
Output
3 3 1 2

We have $\displaystyle \cfrac{36}{11} = 3 + \cfrac{1}{3 + \cfrac{1}{1 + \cfrac{1}{2}}}$.
In this case, $A =(3,\ 3,\ 1,\ 2)$, so you should output these in order. Outputting something like $A = (3,\ 3,\ 0,\ 0,\ 1,\ 2)$ is also accepted.

Sample 2
Input
20 1
Output
20

$\displaystyle \cfrac{N}{M}$ may already be an integer.

Sample 3
Input
10 23
Output
0 2 3 3

$A_0 = 0$ may occur, but you must still output it in this case.

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