【51nod】1011 最大公约数GCD

【51nod】 最大公约数GCD

• 辗转相除法
• 递归

#include
using namespace std;

int gcd(int m, int n) {
	return m % n? gcd(n, m % n) : n;
	//应用辗转相除法
	//m为被除数，n为除数, m % n为余数
	//余数为0时，返回除数n
	//余数不为0时，以除数替代被除数，以余数代替除数 
}

int main() {
	int a, b;
	while(scanf("%d %d", &a, &b) != EOF) {
		int ans = gcd(a, b);
		printf("%dn", ans);
	}
	return 0;
}

• c++库函数 __gcd()的应用

#include
#include
using namespace std;
int main() {
	int a, b;
	while(scanf("%d %d", &a, &b) != EOF) {
		int ans = __gcd(a, b);
		printf("%dn", ans);
	}
	return 0;
}