luogu#B4025. 最大公约数

最大公约数

题目描述

定义两个正整数的最大公约数 gcd(a,b)\gcd(a,b) 为最大的正整数 dd,使得 dd 可以同时整除 aabb

例如,gcd(9,12)=3\gcd(9,12)=3,因为 9÷39\div 312÷312\div 3 的余数是 00,而无法找到一个比 33 更大的正整数满足要求。

现在给定两个正整数 a,ba,b,要求出 gcd(a,b)\gcd(a,b)

输入格式

输入两个正整数 a,ba,b

输出格式

输出 gcd(a,b)\gcd(a,b)

9 12
3
100 1000
100

提示

对于 40%40\% 的数据,1a,b10001\leq a,b\leq 1000

对于所有的数据,1a,b1091\leq a,b\leq 10^9