Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!