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

内容纲要

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

题目描述

输入两个正整数 $x_0, y_0$，求出满足下列条件的 $P, Q$ 的个数：

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

  2. 要求 $P, Q$ 以 $x_0$ 为最大公约数，以 $y_0$ 为最小公倍数。

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

输入格式

一行两个正整数 $x_0, y_0$。

输出格式

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

样例 #1

样例输入 #1

3 60

样例输出 #1

4

提示

$P,Q$ 有 $4$ 种：

  1. $3, 60$。
  2. $15, 12$。
  3. $12, 15$。
  4. $60, 3$。

对于 $100\%$ 的数据，$2 \le x_0, y_0 \le {10}^5$。

【题目来源】

NOIP 2001 普及组第二题

Answer1

这个问题的关键在于理解，由于$P$ 和$Q$ 的最大公约数为$x_0$，且它们的最小公倍数为$y_0$，所以实际上$P$ 和$Q$ 必须是$x_0$ 的倍数，且$P/Q$ 或$Q/P$ 必须是互质的（即除了$x_0$ 外，它们没有其他公约数）。

因此，正确的方法是先计算$y_0$ 相对于$x_0$ 的比值，即$n = y_0 / x_0$，然后找到所有$n$ 的因子（这里的因子指的是能整除$n$ 的数）。对于每一个因子$i$，我们检查如果$i$ 与$n / i$ 互质，那么这对因子就可以形成一对合法的$P, Q$。

这段代码中新增加了一个辅助方法 gcd 用于计算两个数的最大公约数，它是通过欧几里得算法实现的。主方法 countPairs 中的核心逻辑是遍历所有可能的$i$ 值，如果$i$ 是$n$ 的因子，并且$i$ 与$n / i$ 互质（即它们的最大公约数为 1），那么这对因子就符合题目条件。如果$i$ 和$n / i$ 相等，那么这种情况只能算作一对$P, Q$（因为它们是相同的数），否则我们可以通过交换$P$ 和$Q$ 的值来得到另外一对不同的$P, Q$，因此总数翻倍。

public class Main {
    public static void main(String[] args) {
        int x0 = 3; // 示例输入
        int y0 = 60; // 示例输入
        System.out.println(countPairs(x0, y0));
    }

    private static int countPairs(int x0, int y0) {
        int n = y0 / x0; // n 是 y0 除以 x0
        int nn = y0 % x0;
        if (nn != 0) return 0;  // 检查y是否是x的倍数。如果不是，说明不存在满足条件的P,Q对，直接输出 0。
        int count = 0; // 用于存储满足条件的 P, Q 对的数量

        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                // 检查 i 和 n/i 是否互质
                if (gcd(i, n / i) == 1) {
                    // 如果 i*i == n，这种情况只能算一次，因为 P 和 Q 是一样的
                    if (i * i == n) {
                        count++;
                    } else {
                        // 否则，P 和 Q 可以互换位置，所以计数翻倍
                        count += 2;
                    }
                }
            }
        }

        return count;
    }

    // 辅助方法：计算最大公约数（GCD）
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

Answer2

符号约定

我们使用$(a,b)$表示$a,b$这两个数的最大公因数，使用$[a,b]$表示$a,b$这两个数的最小公倍数。

我们使用$a\mid b$表示$a$能整除$b$，或者说$b$能被$a$整除；
我们使用$a\nmid b$表示$a$不能整除$b$，或者说$b$不能被$a$整除。

算术基本定理

任何大于1的整数都可以被分解成若干个素数的幂的乘积，且不计素因子的排列顺序时分解方法是唯一的。

例：$720=2^4\cdot 3^2\cdot 5^1$

上面的操作叫做素因数分解。若将素因子从小到大排列，就得到了标准素数分解式。

最大公因数和最小公倍数与素数分解式有什么联系呢？

举个例子：
我们尝试分解样例中的提到的一组数$12,15$：
$12=2^2\cdot 3^1,\quad 15=3^1\cdot 5^1$

为了方便下面的讨论，尽管$12$没有素因子$5$，$15$没有素因子$2$，但我们还是要把非共有的素因子写成$0$次幂的形式：
$12=2^2\cdot 3^1\cdot 5^0,\quad 15=2^0\cdot 3^1\cdot 5^1$

将两个数素数分解式中每个素因子的指数部分取两个中的最小值，就得到了两个数的最大公因数：
$(12,15)=2^0\cdot 3^1\cdot 5^0=3$

将两个数素数分解式中每个素因子的指数部分取两个中的最大值，就得到了两个数的最小公倍数：
$[12,15]=2^2\cdot 3^1\cdot 5^1=60$

倒着推我们可以发现，要使$(P,Q)=3$且$[P,Q]=60$，$P,Q$这两个数的素数分解式必须满足下面3个条件：

素因子$2$的指数的最大值为$2$，最小值为$0$.$\quad \Rightarrow$ 其中一个素数分解式中$2$的指数为$2$，而另一个为$0$​；

素因子$5$的指数的最大值为$1$，最小值为$0$.$\quad \Rightarrow$ 其中一个素数分解式中$5$的指数为$1$，而另一个为$0$；

素因子$3$的指数的最大值为$1$，最小值为$1$.$\quad \Rightarrow$ 两个素数分解式中$3$的指数均为$1$；

像$2$和$5$这样的，指数在$x_0,y_0$的素数分解式中不同的素因子，能导致$P,Q$可变；而像$3$这样的，指数在$x_0,y_0$的素数分解式中相同的素因子，在$P,Q$中的指数一定是相同的，没法变化。

计算方法

如何快捷地寻找$x_0,y_0$的指数不同的素因子呢？

对$\dfrac{y_0}{x_0}$进行素因数分解，得到的指数大于0的素因子即是导致$P,Q$可变的素因子。
我们只需要统计这样的素因子的数量，就像把每种素因子看成不同的球，要放进$P,Q$这两个不同的袋子里，每一种素因子都有放进$P$和放进$Q$这两种选择。
假设$\dfrac{y_0}{x_0}$的指数大于0的素因子有$n$个，那么就能产生$2^n$对$P,Q$的组合。

如果$x_0$不能整除$y_0$呢？

这表明不存在符合条件的$P,Q$.
反证：
不妨假设存在符合条件的$P\in\mathbb Z_+$，
使得：$x_0$是$P$的因数，那么将有$x_0\mid P$；
使得：$y_0$是$P$的倍数，那么将有$P\mid y_0$；
根据整除的传递性，有$x_0\mid y_0$；
这个结论与题设矛盾，故假设不成立。

于是当$x_0\nmid y_0$时，我们输出0作为答案。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int x = Integer.parseInt(st.nextToken());
        int y = Integer.parseInt(st.nextToken());
        int count = 0;    //统计素因数的个数
        if (y % x != 0) {
            System.out.println(0);
            return;
        } else {
            int q = y / x;
            int cf = 2;    //用来试验整除性的因数
            while (q > 1) {    //等于1时标志着分解完毕
                if (q % cf == 0) {
                    count++;
                    while (q % cf == 0) {    //若能整除就除到底
                        q /= cf;
                    }
                }
                cf++;
            }
        }
        System.out.println(1 << count);    //使用位运算来产生2的方幂
    }
}

解题步骤和思想如下：

  1. 验证条件：首先检查 $y$ 是否是 $x$ 的倍数。如果不是，说明不存在满足条件的 $P, Q$ 对，直接输出 0。

  2. 计算商：计算 $y / x$ 的值，此操作基于最大公约数和最小公倍数的关系：如果 $P, Q$ 的最大公约数为 $x$，最小公倍数为 $y$，那么 $P \times Q = x \times y$。由于 $P, Q$ 都是 $x$ 的倍数，考虑 $P = x \times a, Q = x \times b$，其中 $a, b$ 互质，那么 $a \times b = y / x$。

  3. 质因数分解：通过遍历，对 $y / x$ 进行质因数分解，计算出所有的素因数。每次当发现 $quotient$ 可以被当前的素因数 $currentFactor$ 整除时，就一直除以这个因数，直到不能整除为止。在这个过程中，每发现一个新的素因数，就增加计数器 $count$ 的值。

  4. 计算对数：因为每个素因数可以独立选择分配给 $P$ 或 $Q$（但至少要分配给一个），所以如果有 $n$ 个不同的素因数，就会有 $2^n$ 种分配方式。这是因为每个素因数都有两种选择（分配给 $P$ 或 $Q$），所有素因数的组合就构成了不同的 $P, Q$ 对。最终，通过 $1 << count$ 使用位运算来快速计算 $2^n$，即 $2$ 的 $count$ 次方，输出这个值作为结果。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注