2020牛客寒假算法基础集训营4.A——欧几里得规律 _集训

非淡泊无以明志，非宁静无以致远。这篇文章主要讲述2020牛客寒假算法基础集训营4.A——欧几里得规律相关的知识，希望能为你提供帮助。
【2020牛客寒假算法基础集训营4.A——欧几里得规律】

??题目传送门??
题目描述
欧几里得算法是一种求最大公约数的有效算法，在算法竞赛中很常用。
这个算法的 python 实现如下：

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

现在，如果已知 gcd(a,b) 共递归了 n次，求所有可能的a,b中满足a> b> =0且a+b最小的一组的a与b之和。
输入描述:
第一行一个整数,T。
接下来T行一行一个整数，n。
输出描述:
T行，每行一个整数，代表a+b。
输入

1
0

输出

1

说明
gcd(1,0) 由于 b=0，不会递归，即是递归0次。
输入

1
1

输出

3

说明
gcd(2,1)会递归一次至gcd(1,0)。
备注:

题解

很容易发现规律

AC-Code

#include < bits/stdc++.h>
using namespace std;
#define
typedef long long ll;

const int INF = 0x7fffffff;
const int maxn = 1e5 + 7;

int main()
int T; cin > > T; while (T--)
int n; cin > > n;
ll a = 1, b = 0;
for (int i = 0; i < = n; ++i)
ll temp = b;
b = a;
a = temp + b;

if (n == 0)a = 1, b = 0;
cout < < a + b < < endl;