No.1794 Continued Fraction
タグ : / 解いたユーザー数 87
作問者 :
Kazun
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もしくは右上の雲マークをクリックしてアカウントを作成してください。