计算连分数

题目介绍

呱呱泡蛙今天来介绍一下连分数算法。

怎样把一个数展开成为连分数？很简单，不停地向下取整，再取倒数就可以了。

比如：

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

在这里循环了。于是可以记作：

$$\sqrt{2}=\left[1,2,2,2,2,2,…\right]$$

一般对下标的表述从0开始。这个例子中的连分数第0项是1，第1项是2，以此类推。

直接计算连分数，存在浮点精度问题。比如计算根号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位就会因为浮点精度问题导致计算失败。怎么办？

解决方案是这样的。定义一个有理数结构体：

struct rational
{
    long long p,q;
};

定义一个特殊的结构体：

struct quaderic
{
    struct rational a,b;
};

用来表示全体这种特殊类型的数：

$$a+b\sqrt{d}$$

在计算的时候要注意，有理数加减乘除时，经常需要约分，计算一次约分一次。所以，最大公约数的写法也提供好了：

long long gcd(long long a,long long b)
{
    if(b==0)
    {
        return a;
    }
    return gcd(b,a%b);
}

有了以上工具，请你来计算根号d的连分数展开吧！

输入格式

两个数，d和n。其中，d为正整数，并且不是完全平方数，n表示计算到第n位，而下标从0开始。比如n是0的时候，要计算1位，即第0位。

输出格式

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

输入样例

12 16

输出样例

3 2 6 2 6 2 6 2 6 2 6 2 6 2 6 2 6

样例解释

$$ \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]$$

数据范围

d不超过10000，n不超过200。

Author：呱呱泡蛙