专栏文章

P1029 题解

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

文章操作

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

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

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

题面

输入两个正整数 x0,y0x_0, y_0,求以 x0x_0 为最大公约数,以 y0y_0 为最小公倍数的正整数 P,QP, Q 的个数。(NOIP 2001 普及组第二题)

思路

数学分析

如果 P,QP, Qx0x_0 为最大公约数,那么它们各除以 x0x_0 后一定互素,否则 gcd(P,Q)\gcd(P, Q) 将会大于 x0x_0
我们就可以设 P=mx0,Q=nx0,gcd(m,n)=1P = mx_0, Q = nx_0, \gcd(m, n) = 1
短除法
由图片中的短除法,我们就可以得出 mnx0=y0,mn=y0x0mn \cdot x_0 = y_0, mn = \dfrac{y_0}{x_0}
于是,我们枚举 y0x0\dfrac{y_0}{x_0} 的因数 n,mn, m,如果 gcd(n,m)=1\gcd(n, m) = 1,答案变量增加。

相关例题

已知 gcd(x,y)=6,xy=288\gcd(x, y) = 6, xy = 288,求:x,yx, y

gcd(x,y)=6\gcd(x, y) = 6,设 x=6m,y=6n,gcd(m,n)=1x = 6m, y = 6n, \gcd(m, n) = 1
xy=288xy = 288,得 6m6n=288,mn=86m \cdot 6n = 288, mn = 8
gcd(m,n)=1\gcd(m, n) = 1,得 {m=1,8n=8,1\begin{cases} m = 1, 8\\ n = 8, 1\\ \end{cases}
x=6m,y=6nx = 6m, y = 6n,得 {x=6,48y=48,6\begin{cases} x = 6, 48\\ y = 48, 6\\ \end{cases}

代码

在测试点 4 中,输入为 12 409640964096 不能被 1212 整除,所以不存在满足要求的 P,QP, Q。我们要在代码中写一个特判,当 y0y_0 不能被 x0x_0 整除时,输出 0
CPP
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int x, y;
    cin >> x >> y; // 输入
    if (y % x > 0) // 特判
    {
    	cout << 0;
    	return 0;
	}
    int num = y / x, cnt = 0;
    for (int i = 1; i <= num; ++i) // 枚举 y / x 的因数
    {
        if (num % i == 0 && num % (num / i) == 0)
        {
            if (__gcd(i, num / i) == 1) // 判断 n, m 是否互素
            {
                cnt += 1; // 计数
            }
        }
        
    }
    cout << cnt; // 输出答案
    return 0;
}

评论

2 条评论,欢迎与作者交流。

正在加载评论...