题目描述

老师有一张长方形彩纸，长为 (a) 厘米，宽为 (b) 厘米（均为正整数）。 要求将这张彩纸全部裁剪成若干块完全相同的正方形小纸片，满足：

1. 正方形边长为整数厘米；
2. 裁剪后没有任何剩余，整块长方形恰好被正方形铺满；
3. 希望正方形的边长尽可能大。

请你计算：满足条件的正方形最大边长是多少厘米。

输入格式

一行，两个正整数 (a, b)。

输出格式

一行，一个整数，表示最大边长。

12 18

6

20 25

5

7 13

1

2 3

1

提示

1≤a,b≤1000

提示说明

• 本题核心是求 (a) 和 (b) 的最大公约数，即能同时整除长和宽的最大正整数；
• 当 (a=2、b=3) 时，仅有公因数1，故最大边长为1（裁剪为6块1×1的正方形，恰好铺满无剩余）；
• 枚举法解题思路：从 (\min(a,b)) 向下枚举，第一个能同时整除 (a、b) 的数即为答案。