Continued Fraction

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.

pypy3 解法, 执行用时: 126ms, 内存消耗: 24676K, 提交时间: 2023-04-26 15:48:30

t = int(input())
while t>0:
    x,y = map(int,input().split())
    result = []
    if x==1:
        print('1 0 '+str(y))
    else:
        while x!=1:
            result.append(x//y)
            x,y=y,x%y
        print(str(len(result)-1)+' '+' '.join(map(str,result)))
    t-=1

C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 460K, 提交时间: 2023-03-25 19:10:50

#include<stdio.h>
int main(){
	int T,x,y,n,t,i,a[20];
	for(scanf("%d",&T);T;--T,puts("")){
		for(scanf("%d%d",&x,&y),n=0;y;++n)a[n]=x/y,t=x%y,x=y,y=t;
		for(printf("%d ",n-1),i=0;i<n;++i)printf("%d ",a[i]);
	}
}

Python3 解法, 执行用时: 136ms, 内存消耗: 4804K, 提交时间: 2023-05-11 18:12:43

def dfs(a,b):
    ls.append(a//b)
    if b<=1:
        return
    dfs(b,a%b)
n=int(input())
for i in range(n):
    x,y=map(int,input().split())
    ls=[]
    dfs(x,y)
    print(len(ls)-1,end=' ')
    print(*ls)

详情