P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

• 最大公约数（即 gcd）和最小公倍数（即 lcm）的求法。

该题的关键点在于，两个数的积等于它们最大公约数和它们最小公倍数的积。公式表示为 \(a \times b = \text{gcd}(a,b) \times \text{lcm}(a,b)\)。设作为答案的两个数为 \(x\) 和 \(y\)，我们要使它们同时满足以下三个条件，并统计这样的 \(x\) 和 \(y\) 的个数（\(P,Q\) 含义见题目描述）：

• \(x \times y = P \times Q\)
• \(\text{gcd}(x,y) = P\)
• \(\text{lcm}(x,y) = Q\)

我们可以枚举 \(x\)，判断是否存在满足条件 1 的整数 \(y\)（即，\(x\) 能被 \(P,Q\) 的积整除）。满足第一个条件后，再分别判断当前的 \(x,y\) 是否能够同时满足另外两个条件即可。显然，这种做法会超时。

考虑优化这个程序。我们其实并不需要枚举两次，因为对于不同的 \(x,y\)，交换它们的值一定可以得到另一组与之对应的解。因此，从 \(1\) 到 \(\sqrt{P \times Q}\) 枚举一遍，每发现一组答案就将 \(\text{ans}\) 的值加 \(2\) 即可。

一组 \(x,y\) 有对应解时有条件：\(x,y\) 的值不同。如果它们相同，交换后并不能得到与之对应的另一组数。
当 \(x = y\) 时，易得 \(x = y = \text{gcd}(x,y) = \text{lcm}(x,y)\) 所以要对此进行特判。若 \(P,Q\) 相等，这种情况就存在，\(\text{ans}\) 里要减去 \(1\)。

一些代码实现技巧

• c++里有一个自带的求 \(\text{gcd}\) 的函数叫 __gcd 。
• 当积相同且 \(\text{gcd}\) 相同时，\(\text{lcm}\) 也一定相同，因此只需判断是否满足一、二两个条件即可。

AC代码:

#include<bits/stdc++.h>
using namespace std;
long long m,n,ans;
int main(){cin>>m>>n;if(m==n) ans--;n*=m;//把两数的积存入n中for(long long i=1;i*i<=n;i++){if(n%i==0&&__gcd(i,n/i)==m) ans+=2;}cout<<ans;return 0;
}

公式速记:
\(a \times b = \text{gcd}(a,b) \times \text{lcm}(a,b)\)