给出两个整数，要求求它们的最大公约数

Question

给出两个整数，要求求它们的最大公约数，如果出现负数情况要怎么办呢？

Answer 1

一、题目描述

  循环输入。每组数据，给定两个非负整数 $a$ 和 $b$ $( a, b \le 10^9)$，求两者的最大公约数。当没有任何输入时，程序结束。

二、解题思路

难度：🔴🔴⚪⚪⚪

• 这个问题是最经典的最大公约数问题，我们从最简单的定义出发。
• 如果一个数是 $a$ 的约数（通常也叫因数，因子），同时也是 $b$ 的约数，那么，它称为 $a$ 和 $b$ 的公约数。这样的公约数有很多，其中最大的一个数就成为 $a$ 和 $b$ 的最大公约数。表示为：
• $$gcd(a, b)$$
• 这里介绍四种解法：
• 1）枚举法
• 2）枚举法 + 限界优化
• 3）根号限界法
• 4）辗转相除法

三、扩展阅读

【第22题】给定 a 和 b，求它们的最大公约数 | 辗转相除法_英雄哪里出来-CSDN博客 难度：★★☆☆☆，辗转相除法 https://blog.csdn.net/WhereIsHeroFrom/article/details/118272816