题解 | 最大公约数

//两种写法 原理都是欧几里得算法(辗转相除法)

//递归写法
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <iostream>

using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
int main() {
	int m, n;
	while (scanf("%d%d", &m, &n) != EOF) {
		printf("%d", gcd(m, n));
	}
	return 0;
}

//非递归写法
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
	int m, n,temp;
	while (scanf("%d%d", &m, &n) != EOF) {
		while (m % n != 0) {
			temp = m;
			m = n;
			n = temp % n;
		}
		printf("%d\n", n);
	}

	return 0;
}