侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【数学】最大公约数和最小公倍数问题

GabrielxD
2023-09-21 / 0 评论 / 0 点赞 / 130 阅读 / 508 字
温馨提示:
本文最后更新于 2023-09-26,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


题目描述

输入两个正整数 x0,y0x_0, y_0,求出满足下列条件的 P,QP, Q 的个数:

  1. P,QP,Q 是正整数。

  2. 要求 P,QP, Qx0x_0 为最大公约数,以 y0y_0 为最小公倍数。

试求:满足条件的所有可能的 P,QP, Q 的个数。

输入格式

一行两个正整数 x0,y0x_0, y_0

输出格式

一行一个数,表示求出满足条件的 P,QP, Q 的个数。

样例 #1

样例输入 #1

3 60

样例输出 #1

4

提示

P,QP,Q44 种:

  1. 3,603, 60
  2. 15,1215, 12
  3. 12,1512, 15
  4. 60,360, 3

对于 100%100\% 的数据,2x0,y01052 \le x_0, y_0 \le {10}^5

【题目来源】

NOIP 2001 普及组第二题

解题

方法一:数学

思路

由于 a×b=gcd(a,b)×lcm(a,b)a \times b = \gcd(a, b) \times \mathrm{lcm}(a, b) ,所以在枚举 aa 时可以直接算出 b=xyab = \frac{xy}{a} ,然后再判断这对 a,ba, b 的最大公约数和最小公倍数是否满足条件即可(由于整除会向下取整,所以算出 bb 后要再判断一次 a×b=x×ya \times b = x \times y 是否成立)。

代码

#include <cstdio>

using namespace std;

const int N = 1e5 + 10;
int x, y;
bool vis[N];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

int main() {
    scanf("%d%d", &x, &y);
    int cnt = 0;
    for (int a = x; a <= y; ++a) {
        int b = x * y / a;
        if (a * b != x * y) continue;
        if (gcd(a, b) == x && lcm(a, b) == y) ++cnt;
    }
    printf("%d\n", cnt);

    return 0;
}

参考

0
博主关闭了所有页面的评论