zzuli oj 1062 最大公约数 欧几里得模板

缘起

欧几里得算法是一定要会的，所以找板题切一下. zzuli oj 1062 最大公约数

分析

题目是中文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
【题目描述】
输入两个不大于10的9次方的正整数，输出其最大公约数。 

【输入】
输入两个正整数m和n，数据之间用空格隔开。 

【输出】
输出一个整数，表示m和n的最大公约数。 

【样例输入】
4 6

【样例输出】
2

【限制】
时间限制: 1 Sec  
内存限制: 128 MB

没什么好说的，就是gcd(a,b)=gcd(b,r) 这一套. 给出递归和非递归两种写法

首先是递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int gcd(int m, int n) {return n?gcd(n,m%n):m;} // 就是初中都知道的(a,b)=(b,r)

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int m,n;
	scanf("%d%d", &m,&n);
	printf("%d\n",gcd(m,n));
	return 0;
}

ac情况

2959608 yfsyfsyfs 1062 正确 1044 1 C++/Edit 304 B 2019-08-17 14:06:51 LOCAL

其次是非递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

int gcd(int m, int n) 
{
	int t;
	while(n) // 依旧是(a,b)=(b,r)那一套
	{
		t = n; // 因为n要变了, 所以用临时变量t记下原本的n
		n = m%n;
		m = t;
	}
	return m; // 特别的, n=0, 则直接返回m
}

int main() 
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	int m,n;
	scanf("%d%d", &m,&n);
	printf("%d\n",gcd(m,n));
	return 0;
}

ac情况

2959610 yfsyfsyfs 1062 正确 1044 1 C++/Edit 412 B 2019-08-17 14:09:45 LOCAL

最后说一下，欧几里得算法是log级别复杂度的, 速度很快， 但是这里有必要说一句——用上述算法求出的gcd可能是负值，例如 gcd(-3,2)=-1