最大公约数（更相减损术）
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
题目描述
定义两个正整数的最大公约数 gcd(a,b) 为最大的正整数 d，使得 d 可以同时整除 a 和 b。 例如，gcd(9,12)=3，因为 9÷3 和 12÷3 的余数是 0，而无法找到一个比 3 更大的正整数满足要求。
现在给定两个正整数 a,b，要求出 gcd(a,b)。
输入格式
输入两个正整数 a,b。
输出格式
使用更相减损术输出 gcd(a,b)。
输入输出样例
输入 #1
9 12
输出 #1
3
输入 #2
100 1000
输出 #2
100
AShui0706堂训
- Status
- Done
- Problem
- 15
- Open Since
- 2025-7-6 0:00
- Deadline
- 2025-7-14 23:59
- Extension
- 24 hour(s)