U283401 计算连分数

连分数是一种特殊繁分数。经常用于将无理数分析为“纯粹的数学上的形式”。 我们以 $\sqrt 2$ 为例来展示连分数的展开。具体来说，我们需要对分母部分**向下取整**（提取他的整数部分），剩下小于 $1$ 的部分取倒数，取倒数之后的分母就是下一次展开所需要处理的对象了。 $$ \sqrt{2}=1+\left(-1+\sqrt{2}\right)=1+\frac{1}{1+\sqrt{2}}=1+\frac{1}{2+\left(-1+\sqrt{2}\right)}=1+\frac{1}{2+\frac{1}{1+\sqrt{2}}} $$ 在 $2$ 这里循环了。于是可以记作： $$ \sqrt{2}=\left[1,2,2,2,2,2,…\right] $$ 一般对下标的表述从 $0$ 开始。这个例子中的连分数第 $0$ 项是 $1$ ，第 $1$ 项是 $2$ ，以此类推。 但是直接计算连分数，存在浮点精度问题。比如计算 $\sqrt 7$ 的连分数展开，本来应该拥有一个稳定的循环节。但是如果直接用浮点类型计算，你会见到： ``` 2 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 1 1 4 1 2 684 8 3 15 ``` 一般不超过40位就会因为浮点精度问题导致计算失败。怎么办？ 我们可以定义一个有理数结构体： ```c++ struct rational { long long p,q; }; ``` 来定义有理数 $\dfrac{p}{q}$ ，在此基础上定义它的四则运算。 在计算的中间过程会出现 $a+b\sqrt d$ 的连分数形式，其中 $a,b$ 是有理数。我们可以考虑采用以下定义方式： ``` struct quaderic { struct rational a,b; }; ``` 请你根据上述提示，计算 $\sqrt d$ 的连分数的展开。

给定无理数 $\sqrt d$ （其中 $d$ 是正整数且非完全平方数），请计算其连分数展开的形式。

输入两个数，正整数 $d$ 和自然数 $n$。其中 $d$ 不是完全平方数，需要计算其连分数到第 $n$ 位 (**下标从 $0$ 开始**，其中第 $0$ 位显然就是 $\sqrt d$ 的整数部分)。

输出一行，共 $n+1$ 个数，是 $\sqrt d$ 的连分数展开到第 $n$ 位，每两个数之间有一个空格。

### 样例解释 根据题目描述进行处理，每一次向下取整提取其整数部分，小于 $1$ 的部分取倒数之后的分母即为下一次展开的目标。 $$ \sqrt{12}=3+(-3+\sqrt{12})=3+\frac{1}{\frac{3+\sqrt{12}}{3}}\\=3+\frac{1}{2+\frac{-3+\sqrt{12}}{3}}\\=3+\frac{1}{2+\frac{1}{3+\sqrt{12}}}=3+\frac{1}{2+\frac{1}{6+(-3+\sqrt{12})}} $$ 不难看出存在循环节，可以记作： $$ \sqrt{12}=\left[3,2,6,2,6,2,…\right] $$ ### 数据范围 对于 $100\%$ 的数据有： $d\le 10000,n\le200$ 。