Preparing NOJ

# Continued Fraction

1000ms 262144K

## Description:

A continued fraction is an expression of the form: $$a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{\ddots+\dfrac{1}{a_n}}}}$$ where $a_0,a_1,\ldots,a_n$​ are nonnegative integers.

Given a fraction $\frac{x}{y}$($x,y$ are positive integers), please expand it into a continued fraction.

## Input:

The first line contains an integer $T$ ($1\le T\le 10^3$), denoting the number of test cases.

The only line of each test case contains two integers $x, y$ ($1\le x,y\le 10^9$), denoting a fraction $\frac x y$. It's guaranteed that $\gcd(x,y)=1$.

## Output:

For each test case, output one line: first an integer $n$ denoting the height of the continued fraction, then $n+1$ integers denoting $a_0,\ldots,a_n$. Your solution should gurarantee that $0\le n\le 100$, $0\le a_i\le 10^9$.

If there are multiple valid solutions, you only need to output one of them.

## Sample Input:

2
105 38
1 114


## Sample Output:

4 2 1 3 4 2
1 0 114


## Note:

For the convenience of you, we give explanation of sample: $$\frac{105}{38}=2+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{4+\dfrac 1 2}}}$$

$$\frac{1}{114}=0+\dfrac{1}{114}$$

Info

Provider CodeForces Gym

Code GYM103366B

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:45

Related

Nothing Yet