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

· · 题解

题目大意

给定 x_0, y_0，求有序数对 (P, Q) 使得 (P, Q) = x_0, [P, Q] = y_0 的数量。

思路

首先一看到这是一道有关于 \gcd 和 \operatorname{lcm}（即最大公约数和最小公倍数）的问题，就简单地把欧几里得算法（即辗转相除（减）法）浅讲一下吧。

欧几里得算法

其实这就是一个很简单的港式大家记住就行：

(a,b) = (b, a - b) (a > b)

那么我们把这个操作进行很多很多次，直到其中一个为 0，那么我们就得到这样一个形式 (a,b) = (0, k) = k，也就得出了 (a,b) 的值。

小结论

下面是一个再次体重要用到的结论：

(a,b) \times [a,b] = ab

随手证明一下吧。我们设：

a=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n} b=p_1^{\beta_1}p_2^{\beta_2}\dots p_n^{\beta_n}

这里，p_1,p_2\dots p_n 为 a, b 的所有的不同质因数。

由于

(a,b)=\prod_{i=1}^{n} p_i^{\min(\alpha_i,\beta_i)} [a,b]=\prod_{i=1}^{n} p_i^{\max(\alpha_i,\beta_i)}

代入到左式

(a,b) \times [a,b]=\prod_{i=1}^{n} p_i^{\alpha_i+\beta_i} = ab

得证。

接下来，我们正式开始做这道题。

首先，题目给出了 x_0, y_0，那么我们根据这个，就可以求出 P\times Q 的值，接下来，对于每一组 (P, Q)，检验 (P, Q) 是否等于 x_0，若成立，即可将其计入正确组数。

考虑优化。

由于对于每一组 (a, b) 满足题意（即 ab = PQ, (a,b) = x_0，那么 (b,a) 也应当满足题意。所以我们只需枚举到 \sqrt{PQ}，并检验 a 的正确性，假若正确，我们就能将这两组均计入可行方案。（建议不要直接讲循环的终止条件改为 i <= sqrt(n)，而是 i * i <= n，这样精度会好些）

再者，有一些数据会使得 P=Q，那就没有上述交换的必要，所以只能加上一组。

代码

接下来就是代码咯

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b) {return a * b / gcd(a, b);}

int main() {
    ll x, y, ans;
    cin >> x >> y; x *= y;
    for(ll i = 1; i * i <= x; i++) {
        if(!(x % i)) {
            ll a = i, b = x/i;
            if(lcm(a, b) == y) {
                if(a != b) ans++;
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}