Preparing NOJ

Continued Fraction

1000ms 262144K


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.


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$$$.


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:

105 38
1 114

Sample Output:

4 2 1 3 4 2
1 0 114


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} $$$$$$


CodeForces Gym

Provider CodeForces Gym

Origin 2021 Jiangxi Provincial Collegiate Programming Contest

Code GYM103366B


Submitted 0

Passed 0

AC Rate 0%

Date 10/25/2021 22:31:45


Nothing Yet