自动搬运

查看原文

来自洛谷，原作者为

	樱雪喵 无尽欺骗，无限祈愿 | AFOed | qq: 3480681868

搬运于2025-08-24 21:20:06，当前版本为作者最后更新于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$ 了，计算会重复。