1191. 欧几里得

欧几里得算法是一种求最大公约数的有效算法,在算法竞赛中很常用。

这个算法的 Python 实现如下:

def gcd(a,b): if b == 0: return a return gcd(b,a%b)

现在,如果已知 gcd(a,b)gcd(a,b) 共递归了 nn 次,求所有可能的 a,ba,b 中满足 a>b0a>b \geq 0a+ba+b 最小的一组的 aabb 之和。

输入

第一行一个整数 T (1T81)T \ (1≤T≤81)

接下来 TT 行一行一个整数 n (0n80)n \ (0≤n≤80)

输出

TT 行,每行一个整数,代表 a+ba+b

样例

标准输入 复制文本
1
0
标准输出 复制文本
1
标准输入 复制文本
1
1
标准输出 复制文本
3

提示

gcd(2,1)gcd(2,1) 会递归一次至 gcd(1,0)gcd(1,0)

来源

2020 牛客寒假算法基础集训营

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 81
通过 37