专栏文章

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

GGoldenSTEVE7
P1029题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miq9rlh4
此快照首次捕获于
2025/12/04 01:16
3 个月前
此快照最后确认于
2025/12/04 01:16
3 个月前
查看原文

题目大意

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

思路

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

欧几里得算法

其实这就是一个很简单的港式大家记住就行：
(a,b)=(b,a−b)(a>b) (a,b) = (b, a - b) (a > b)
那么我们把这个操作进行很多很多次，直到其中一个为 00，那么我们就得到这样一个形式 (a,b)=(0,k)=k(a,b) = (0, k) = k，也就得出了 (a,b)(a,b) 的值。

小结论

下面是一个再次体重要用到的结论：
(a,b)×[a,b]=ab(a,b) \times [a,b] = ab
随手证明一下吧。我们设：
a=p1α1p2α2…pnαna=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n} b=p1β1p2β2…pnβnb=p_1^{\beta_1}p_2^{\beta_2}\dots p_n^{\beta_n}
这里，p1,p2…pnp_1,p_2\dots p_n 为 a,ba, b 的所有的不同质因数。
由于
(a,b)=∏i=1npimin⁡(αi,βi)(a,b)=\prod_{i=1}^{n} p_i^{\min(\alpha_i,\beta_i)} [a,b]=∏i=1npimax⁡(αi,βi)[a,b]=\prod_{i=1}^{n} p_i^{\max(\alpha_i,\beta_i)}
代入到左式
(a,b)×[a,b]=∏i=1npiαi+βi=ab(a,b) \times [a,b]=\prod_{i=1}^{n} p_i^{\alpha_i+\beta_i} = ab
得证。
接下来，我们正式开始做这道题。
首先，题目给出了 x0,y0x_0, y_0，那么我们根据这个，就可以求出 P×QP\times Q 的值，接下来，对于每一组 (P,Q)(P, Q)，检验 (P,Q)(P, Q) 是否等于 x0x_0，若成立，即可将其计入正确组数。
考虑优化。
由于对于每一组 (a,b)(a, b) 满足题意（即 ab=PQ,(a,b)=x0ab = PQ, (a,b) = x_0，那么 (b,a)(b,a) 也应当满足题意。所以我们只需枚举到 PQ\sqrt{PQ}，并检验 aa 的正确性，假若正确，我们就能将这两组均计入可行方案。（建议不要直接讲循环的终止条件改为 i <= sqrt(n)，而是 i * i <= n，这样精度会好些）
再者，有一些数据会使得 P=QP=Q，那就没有上述交换的必要，所以只能加上一组。

代码

接下来就是代码咯
CPP
#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;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...