最大公约数和最小公倍数问题

在编程中，常常会遇到使用最大公约数与最小公倍数的情况，而这个模块对于初学小白来说逻辑有点复杂，接下来我将介绍两种常用的实现方式。

方法一 直接使用函数

那么如何实现呢？在C++的 algorithm 库中有一个函数： __gcd

对于其使用（非常方便）给出如下示例代码：

#include <iostream>
#include <algorithm> 
using namespace std;
int a, b;
int main() {
    cin >> a >> b;
    int ans = __gcd(a, b); //注意！这里有双下划线（拼写_ _ g c d），千万别漏!
    cout << ans << endl;
    return 0;
}

好了，使用就是这样。优点是使用方便，但很大一个问题就是（非OIer忽略）——NOIP明确声明不支持一切以双下划线开头的函数、命名空间等（自己定义的不算）

那么就需要我们方法二出场啦！

方法二 欧几里得算法

哈哈，听起来很深奥对不对？实际上，它有个更为简单的名字———辗转相除法。相信这个有点数学基础的都该听过吧？实际也很简单。

话不多说，上代码！

int gcd(int a, int b) { //这里就不附完整代码了，方法类同
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

至于证明这里就不给出了，感兴趣的小伙伴可以自己百度哦！

最后，最小公倍数咋求呢？

直接给出公式，推导很简单，可以自己试试。

$$\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$$

例题

题目链接：https://www.luogu.com.cn/problem/P1029

先分析一下题目：

给出两数的gcd和lcm，求两者方案数。

那么如何求解呢？

首先，想到双重循环枚举，当然可以，所以……TLE 了。

那么换一种算法，优化方法：

既然两数的乘积可以由输入得到（见上面知识分析），那么就可以通过 n / i * m （n，m分别为输入，i为枚举数） 来得到另外一个数。 如上即为基本思路。 但为了避免程序超时（对的，这样还是超时的），我们只能枚举一半，即 i * i <= n * m 。这样就能避免超时。

而每一组数值都被计算两遍（见样例），那么再找到一组符合情况的答案时，ans需要加2。

好啦，这就对了。

并不是，想想还有什么没考虑到？ 就是完全平方数！即 i * i == n * m 时，需要特判： if (n == m) ans--; 这样，答案就完全正确了。

AC代码如下：

#include <iostream>
#include <algorithm>
using namespace std;
int n, m, ans;
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	cin >> n >> m;
	if (n == m) {
		ans--;
	}
	for(int i = 1; i * i <= n * m; i++) {
		if (n * m % i == 0 && gcd(i, m * n / i)== n) { //想用__gcd函数的把这里改下就可，前面定义可以去掉
			ans += 2;
		}
	}
	cout << ans << endl;
	return 0;
}