题目链接：https://www.luogu.com.cn/problem/P1029
题目描述
输入 \(2\) 个正整数 \(x_0,y_0(2 \le x_0 \lt 100000,2 \le y_0 \le 1000000)\) ，求满足下列条件的 \(P,Q\) 的个数。
条件：
- \(P,Q\) 是正整数；
- 要求 \(P,Q\) 以 \(x_0\) 为最大公约数，以 \(y_0\) 为最小公倍数。
试求：满足条件的所有可能的 \(2\) 个正整数的个数。
输入格式
\(2\) 个正整数 \(x_0,y_0\)
输出格式
\(1\) 个数，表示求出满足条件的 \(P,Q\) 的个数
问题分析
这道题目虽然命名为《最大公约数和最小公倍数问题》并且它的确可以用最大公约数和最小公倍数的解法做，但是这道题目也可以用分解质因数的方法来解决。
下面分两种方法来解决这个问题：
解法1 GCD+枚举
这个GCD其实就是“最大公约数”（greatest common divisor）的简写。
首先，对于给我们的两个数 \(x_0\) 和 \(y_0\) ，如果 \(x_0\) 不能整除 \(y_0\) ，那么答案肯定是 \(0\) 个。
不然，我们就从 \(x_0\) 到 \(y_0\) 一路枚举 \(P\) ，根据 \(P\) 我们能够得到 \(Q\) 为 \(x_0 \times y_0 / P\) 。
当然此时的 \(Q\) 不一定是合法的,
\(Q\) 合法当且仅当 \(GCD(P,Q) = x_0\) 。
然后统计一下当 \(P\) 在区间 \([x0,y0]\) 范围内有多少个合法的 \(Q\) 即可。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
long long x, y;
long long gcd(long long a, long long b) {
if (b == 0) return a;
return gcd(b, a%b);
}
int main() {
cin >> x >> y;
if (y % x) puts("0");
else {
int cnt = 0;
for (long long p = x; p <= y; p ++) {
if (y % p || p % x) continue; // P必须满足能被x0整除，同时能整除y0
long long q = x * y / p;
if (gcd(p, q) == x) cnt ++;
}
cout << cnt << endl;
}
return 0;
}
然而这道题目还有更快的解法，这就是我接下来要介绍的：
解法2 分解质因数
我们以 “分解质因数” 的方法来解决这个问题。
首先，如果 \(x0\) 不能整除 \(y0\) ，那么答案肯定为 \(0\) ，直接输出 \(0\) 即可。
其次，我们令 \(n = y_0 / x_0\) ，然后对 \(n\) 进行质因数分解，假设对 \(n\) 进行质因数分解的表达式为：
\(n = a_1^{b_1} \times a_2^{b_2} \times \dots \times a_m^{b_m}\)
那么我们知道，对于其中的任意一个 \(a_i\) ，它要么归到 \(P\) ，要么归到 \(Q\) ，不可能有 \(1\) 个 \(a_i\) 归到 \(P\) ，而另一个 \(a_i\) 归到 \(Q\) （因为这个时候他们的最大公约数就变成了 \(x0 \times a_i\)） ，所以对于这 \(m\) 个 \(a_i\) ，他们要么都归到 \(P\) ，要么都归到 \(Q\) ，所以总的方案数就是 \(2^m\) 。
实现代码如下（代码中我用 \(cnt\) 来表示不同的质因数个数）：
#include <bits/stdc++.h>
using namespace std;
int x, y, n, m;
int main() {
cin >> x >> y;
if (y % x) puts("0");
else {
n = y / x;
int a = sqrt(n); // 求平方根
for (int i = 2; i <= a; i ++) {
if (n % i == 0) {
m ++;
while (n % i == 0) n /= i;
}
}
if (n > 1) m ++;
cout << (1<<m) << endl;
}
return 0;
}
学过位运算的同学应该清楚，代码中的 \(1<<m\) 其实表示的就是 \(2^m\) ，而这就是我们的答案了。