wzk的欧几里得 - 题目

内存限制：512 MiB 时间限制：1000 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： nocriz🦆

提交提交记录统计测试数据讨论

wzk很喜欢欧几里得算法。欧几里得算法是一种用来求最大公约数的常用算法，它的一种 C++ 递归实现如下：

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

现在我们已知 gcd(a, b) 这个函数共递归了 $n$ 次，求所有满足 $a > b \ge 0$ 的可能的 $a,\ b$ 中 $a + b$ 最小的一组的 $a$ 与 $b$ 之和。

你需要处理 $T$ 组询问，也就是对 $T$ 个不同的 $n$ 给出各自的 $a + b$ 的最小值。

第一行一个正整数 $T$ ，表示共有 $T$ 组询问。

接下来 $T$ 行，每行一个非负整数 $n$ 。

输出 $T$ 行，每行一个整数，表示 $a + b$ 的最小值。

1
0

1
1

$1 \le T \le 81$

$0 \le n \le 80$

提示：

对于样例1，考虑 gcd(1, 0) ，由于 $b = 0$ ，不会递归，即是递归 $0$ 次。

对于样例2，考虑 gcd(2, 1) ，会递归一次至 gcd(1, 0) 。

编辑器加载中 …

或者，上传代码文件

#1132. wzk的欧几里得