src2020/1664_gongyue
James b602b04036 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00
..
doc 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00
test 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00
Readme.md 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00
main.cpp 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00
main.exe 『入门』(递归专题)最大公约数之辗转相除法 2020-04-24 23:58:28 +08:00

Readme.md

『入门』(递归专题)最大公约数之辗转相除法

[问题描述]

  辗转相除法又名欧几里德算法Euclidean algorithm乃求两个正整数之最大公因子的算法。它是已知最古老的算法其可追溯至3000年前。而在中国则可以追溯至东汉出现的《九章算术》。

教学案例,必须使用递归函数完成求解!

  输入两个正整数n和m均小于10^9。求解n和m的最大公约数。

[输入格式]
  一行,两个整数,空格间隔。

[输出格式]
  一个整数值n和m的最大公约数。

[输入样例]
12 21

[输出样例]
3