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

樱雪喵 · 2020-02-01 19:20:39 · 题解

upd on 2020/06/12：修改了部分解释不够清楚和有歧义的地方。
upd on 2022/07/21：添加了 Latex。

前置知识

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

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

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

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

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

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

一些代码实现技巧：

• c++ 里有一个自带的求 \gcd 的函数叫 __gcd 。upd：现在 NOIP 已经可以使用了。

• 当积相同且 \gcd 相同时，\operatorname{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<=sqrt(n);i++){
        if(n%i==0&&__gcd(i,n/i)==m) ans+=2;
    }
    cout<<ans;
    return 0;
}

评论区常见问题统一回答：

Q：\gcd 是什么？
A：是“最大公约数”的缩写。同理，\operatorname{lcm} 是“最小公倍数”的缩写。

Q：代码中为什么枚举到 \sqrt{n}？
A：前文提到，我们要避免重复，因此循环时只算 x\le y 的情况。当 x=y 时，x=\sqrt{n}。再使 x 变大就会使 x>y 了，计算会重复。