欧几里得算法是一种求最大公约数的有效算法,在算法竞赛中很常用。
这个算法的 Python 实现如下:
def gcd(a,b):
if b == 0:
return a
return gcd(b,a%b)
现在,如果已知 共递归了 次,求所有可能的 中满足 且 最小的一组的 与 之和。
输入
第一行一个整数 。
接下来 行一行一个整数 。
输出
行,每行一个整数,代表 。
样例
标准输入 复制文本 |
1 0 |
标准输出 复制文本 |
1 |
标准输入 复制文本 |
1 1 |
标准输出 复制文本 |
3 |
提示
会递归一次至 。
来源
2020 牛客寒假算法基础集训营