2021 ICPC 江西省大学生程序设计竞赛 签到 B.K.L

B.Continued Fraction

A continued fraction is an expression of the form:

a 0 + 1 a 1 + 1 a 2 + 1 ⋱ + 1 a n a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{\ddots+\dfrac{1}{a_n}}}} a0​+a1​+a2​+⋱+an​1​1​1​1​

where a 0 , a 1 , … , a n a_0,a_1,\ldots,a_n a0​,a1​,…,an​ are nonnegative integers.

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

要求计算一个玄学的式子，队友速签。

观察样例形式，实际上每次都是在交换分子分母，然后假分数化为带分数的过程，每次保存 x y \frac xy yx​即可。

实际上就是模拟辗转相除法的过程，可以直接魔改GCD模板或者一个while循环跑下来即可。

贴一个队友的递归版：工口姐姐的博客

#include 
#define int long long
using namespace std;

const int N = 1e6 + 10;
int ans[N];

inline void solve(){
    int x, y, cnt = 0; cin >> x >> y;
    while(y){
        int now = x / y;
        ans[++cnt] = now, x -= now * y;
        swap(x, y);
    }
    cout > x2 >> y2;
        a[x1]++, a[x2]--;
    }
    for(int i = 1; i