B3736 [信息与未来 2018] 最大公约数

屈老师

[信息与未来 2018] 最大公约数

题目描述

输入三个正整数 $x,y,z$，求它们的最大公约数（Greatest Common Divisor）$g$：最大的正整数 $g ≥1$，满足 $x,y,z$ 都是 $g$ 的倍数，即 $(x \bmod g) = (y \bmod g) = (z \bmod g) = 0$。

输入格式

输入一行三个正整数 $x,y,z$。

输出格式

输出一行一个整数 $g$，表示 $x,y,z$ 的最大公约数。

样例 #1

样例输入 #1

12 34 56

样例输出 #1

样例 #2

样例输入 #2

28 70 28

样例输出 #2

提示

样例解释

样例 $1$

$12 = 2 × 6, 34 = 2 × 17, 56 = 2 × 28, g = 2$。

样例 $2$

$28 = 14 × 2, 70 = 14 × 5, 28 = 14 × 2,g = 14$。

数据规模

所有数据满足 $1 ≤ x,y,z ≤ 10⁶$。

本题原始满分为 $15\text{pts}$。

屈老师

#include <iostream>
using namespace std;
int main() {
	int a1, a2, a3;
	cin >> a1 >> a2 >> a3;
	while (a1%a2)
	{
		int temp = a1%a2;
		a1 = a2;
		a2 = temp;
	}

	while (a3 % a2)
	{
		int temp = a3 % a2;
		a3 = a2;
		a2 = temp;
	}

	cout << a2;
	return 0;
}

陈锦嘉

666