14359: 【原4359】小A写代码

题目

题目描述

author: Mighty-A 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4359

Description

小A在程设课上学习了递归算法。 课后作业中有一道题目要求两个正整数的最大公约数。 小A没有学过数论，想了很久也想不出来怎么写代码求出两个数的最大公约数。 心态爆炸的小A决定去问问小B 可是小B忙着写数分，直接把自己的AC代码发给小A 小A想起来助教说过不能copy代码。 于是小A努力去理解小B的代码，并整理思路记成笔记。

下面是小A的笔记： 两个整数a, b 如果a和b相等，那么a,b的最大公约数是平凡的。 如果a大于b，那么 a和b的最大公约数 与 a-b和b的最大公约数是一样的 请你也利用递归求解最大公约数（可以不采用小A的做法，如果你有更好的方法的话） 请使用给出的模板，完成其中TODO部分。

```

include

using namespace std; int gcd(int a, int b) { // TODO }

int main() { int a, b; cin >> a >> b; cout << gcd(a, b) << endl; return 0; } ```

Input Format

输入 第一行：a b

Output Format

输出 第一行：a,b的最大公约数

Sample Input

8 12

Sample Output

4

Limits

1<=a<=b<=100000

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！