FractionConstructionProblem - 题解

标签与难度

标签: 数论, 扩展欧几里得算法, 构造, 线性筛, 质因数分解难度: 1800

题目大意喵~

哈喽，各位算法探险家们，喵~ 今天我要带大家解决一个关于分数的构造问题，听起来就很有趣对不对？

题目是这样哒：对于每一组查询，我们都会拿到两个正整数 $a$ 和 $b$ 。你的任务呢，就是像变魔术一样，找出四个正整数 $c, d, e, f$ ，让它们满足下面这些奇妙的条件：

等式要成立： $\frac{c}{d} - \frac{e}{f} = \frac{a}{b}$
分母要更小： $d < b$ 并且 $f < b$
分子可以很大： $c$ 和 $e$ 的值在 $1$ 到 $4 \times 10^{12}$ 之间。
$a$ 和 $b$ 的范围是 $1$ 到 $2 \times 10^6$ 。

如果能找到这样的一组 $c, d, e, f$ ，就把它们开心地打印出来。如果无论怎么抓破猫耳朵都找不到，那就只好输出 -1 -1 -1 -1 啦。

解题思路分析

拿到这个问题，我的胡须都兴奋地翘起来了呢！这是一个典型的构造题，需要我们运用一些数论知识来找到解。我们先把那个等式通分一下，看看能不能发现什么线索，喵~

\frac{c}{d} - \frac{e}{f} = \frac{cf - de}{df} = \frac{a}{b}

这个形式告诉我们，cf - de 和 df 的比值应该等于 a 和 b 的比值。为了简化问题，一个很自然的想法就是，我们能不能直接让 $df$ 和 $b$ 产生某种联系，比如让 $df$ 是 $b$ 的倍数？

最简单的想法，就是让 $df$ 等于 $b$ 吗？不对，题目要求 $d<b$ 和 $f<b$ 呢。不过，我们可以从这里出发，把问题分成两种情况来讨论，就像猫咪面对两条路，要选择走哪一条一样！

Case 1: $a$ 和 $b$ 不互质 (简单情况喵~)

当 $a$ 和 $b$ 有大于 1 的最大公约数时，问题会变得非常简单哦！设 $g = \gcd(a, b)$ ，并且 $g > 1$ 。我们可以把原式右边先约分一下：

\frac{a}{b} = \frac{a/g}{b/g}

现在我们的目标是构造 $\frac{c}{d} - \frac{e}{f} = \frac{a/g}{b/g}$ 。

一个超级巧妙的构造方法是，让 $d$ 和 $f$ 相等！比如说，我们令 $d = f = b/g$ 。因为 $g > 1$ ，所以 $b/g < b$ ，这完美满足了 $d<b$ 和 $f<b$ 的条件，太棒啦！

代入我们的选择，等式就变成了：

\frac{c}{b/g} - \frac{e}{b/g} = \frac{c-e}{b/g} = \frac{a/g}{b/g}

两边都乘以 $b/g$ ，就得到 $c - e = a/g$ 。我们需要找到两个正整数 $c$ 和 $e$ 满足这个式子。这可太容易了，就像从罐头里拿小鱼干一样简单！我们可以选一个非常简单的解，比如令 $e=1$ ，那么 $c = a/g + 1$ 。因为 $a, g$ 都是正整数，所以 $c$ 和 $e$ 也肯定是正整数。

所以，当 $\gcd(a, b) > 1$ 时，我们找到了一组解： $c = a/g + 1$ , $d = b/g$ , $e = 1$ , $f = b/g$ 。

Case 2: $a$ 和 $b$ 互质 (有点挑战的情况呐)

如果 $a$ 和 $b$ 互质，即 $\gcd(a, b) = 1$ ，上面的方法就不行了，因为 $g=1$ 会导致 $d=b$ ，不满足 $d<b$ 的说。这时，我们需要回到最初的思路： $\frac{cf-de}{df} = \frac{a}{b}$ 。

一个直接的构造是令 $df = b$ 并且 $cf - de = a$ 。要满足 $df=b$ 且 $d, f < b$ ，意味着 $d$ 和 $f$ 必须是 $b$ 的两个大于 1 的真因子。这就要求 $b$ 必须是一个合数。如果 $b=1$ 或者 $b$ 是一个质数，我们是找不到这样的 $d,f$ 的，所以这种情况下无解。

现在我们来看 $cf - de = a$ 。这是一个关于变量 $c$ 和 $e$ 的线性丢番图方程。它有解的充要条件是 $\gcd(f, -d)$ 能够整除 $a$ ，也就是 $\gcd(f, d)$ 要能整除 $a$ 。但是，我们现在是在 $\gcd(a, b) = 1$ 的情况下讨论。因为 $d,f$ 都是 $b$ 的因子，所以 $a$ 与 $d,f$ 都没有公因子。因此，要让 $\gcd(d, f)$ 整除 $a$ ，唯一的可能性就是 $\gcd(d, f) = 1$ 。

所以，问题转化成了：

找到 $b$ 的两个大于 1 的、互质的因子 $d$ 和 $f$ ，使得 $df = b$ 。
如果找到了，就用它们来解方程 $cf - de = a$ 。

如何找到互质的因子 $d$ 和 $f$ 呢？ 如果一个数 $b$ 可以被分解成两个大于 1 且互质的数相乘，那它必须拥有至少两个不同的质因子。如果 $b$ 只是某个质数 $p$ 的幂（ $b=p^k, k \ge 2$ ），那么它的任何两个大于1的因子（比如 $p^i$ 和 $p^j$ ）都必然有公因子 $p$ ，不可能互质。

所以，当 $\gcd(a,b)=1$ 时，有解的一个必要条件是： $b$ 必须拥有至少两个不同的质因子。我们可以用线性筛预处理出 $2 \times 10^6$ 内所有数的最小质因子（Smallest Prime Factor, SPF）。对于一个给定的 $b$ ，我们找到它的最小质因子 $p$ 。然后，我们把 $b$ 中所有的因子 $p$ 都提出来，形成我们的第一个因子 $d$ 。也就是 $d = p^k$ ，其中 $p^k$ 是 $p$ 在 $b$ 的质因数分解中的最高次幂。剩下的部分就是 $f = b/d$ 。通过这种构造，d 的质因子只有 $p$ ，而 f 的质因子中没有 $p$ ，所以 $d$ 和 $f$ 天然互质！如果这样构造出来的 $f=1$ ，就说明 $b$ 本身就是 $p$ 的幂，无解。否则，我们就成功找到了需要的 $d$ 和 $f$ ！

如何求解 $cf - de = a$ 呢？ 这就要请出我们的好朋友——扩展欧几里得算法（exgcd）啦！我们可以用 exgcd 求解方程 $fx + dy = \gcd(f, d)$ 。因为我们已经保证了 $\gcd(f,d)=1$ ，所以我们解的是 $fx + dy = 1$ 。设 exgcd 给了我们一组解 $(x_0, y_0)$ 。

那么对于方程 $cf - de = a$ ，我们可以构造出两组可能的解：

从 $f \cdot c - d \cdot e = a$ 出发。一个特解是 $c = a \cdot x_0$ ， $e = -a \cdot y_0$ 。如果 $x_0 > 0$ 且 $y_0 < 0$ ，那么 $c = a x_0 > 0$ ， $e = -a y_0 > 0$ ，我们直接就找到了一组正整数解！此时的答案就是 $(c, d, e, f) = (a x_0, d, -a y_0, f)$ 。
如果上面那组解不是正数解（即 $x_0 < 0, y_0 > 0$ ），怎么办呢？我们可以把原式变形成 $\frac{e}{f} - \frac{c}{d} = \frac{-a}{b}$ ，然后解 $de - cf = a$ 。同样利用 $fx_0 + dy_0 = 1$ ，我们可以构造出这个方程的解： $e = a \cdot y_0, c = -a \cdot x_0$ 。因为 $y_0 > 0$ 且 $x_0 < 0$ ，所以 $e = a y_0 > 0$ ， $c = -a x_0 > 0$ 。这又是一组正整数解！此时的答案是 $(c, d, e, f) = (-a x_0, f, a y_0, d)$ 。注意 $d, f$ 的位置也交换了哦！

因为对于 $fx_0+dy_0=1$ ( $f,d>1$ )， $x_0$ 和 $y_0$ 必定异号，所以上面两种情况总有一种能给我们提供一组正整数解。问题解决啦，喵~

总结一下我们的策略：

计算 $g = \gcd(a,b)$ 。
若 $g>1$ ，使用简单构造法。
若 $g=1$ $g = 1$ ，检查 $b$ $b$ 是否有至少两个不同质因子。
- 若没有（ $b=1$ , $b$ 是质数, $b=p^k$ ），则无解。
- 若有，分解出互质的 $d, f$ ，然后用 exgcd 求解。根据 exgcd 返回解的符号，选择两种构造方式中的一种。

代码实现

下面是我根据上面的思路，精心编写的代码哦！注释写得很详细，希望能帮助你理解，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 使用 long long 防止 c, e 溢出
using int64 = long long;

// 最大范围是 2e6，稍微开大一点防止边界问题
const int MAX_B = 2000000 + 5;
// spf[i] 存储 i 的最小质因子 (Smallest Prime Factor)
int spf[MAX_B];
std::vector<int> primes;

// 线性筛预处理所有数的最小质因子
void linear_sieve() {
    for (int i = 2; i < MAX_B; ++i) {
        if (spf[i] == 0) {
            spf[i] = i;
            primes.push_back(i);
        }
        for (int p : primes) {
            if (p > spf[i] || (int64)i * p >= MAX_B) {
                break;
            }
            spf[i * p] = p;
        }
    }
}

// 扩展欧几里得算法
// 求解 a*x + b*y = gcd(a, b)
// 返回 gcd(a, b)，并通过引用修改 x 和 y 的值
int64 exgcd(int64 a, int64 b, int64& x, int64& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int64 d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

// 解决单个查询的函数
void solve() {
    int64 a, b;
    std::cin >> a >> b;

    int64 g = std::gcd(a, b);

    if (g > 1) {
        // Case 1: a 和 b 不互质，使用简单构造法
        // c/d - e/f = (a/g)/(b/g)
        // 令 d = f = b/g, 则 c - e = a/g
        // 取 e=1, c=a/g+1 即可
        int64 c = a / g + 1;
        int64 d = b / g;
        int64 e = 1;
        int64 f = b / g;
        std::cout << c << " " << d << " " << e << " " << f << "\n";
    } else {
        // Case 2: a 和 b 互质
        if (b == 1) {
            // b=1, d,f 必须是正整数且 < 1，不可能
            std::cout << "-1 -1 -1 -1\n";
            return;
        }

        // 找到 b 的最小质因子 p
        int p = spf[b];
        // 构造 d = p^k
        int64 d_val = 1;
        int64 temp_b = b;
        while (temp_b % p == 0) {
            d_val *= p;
            temp_b /= p;
        }
        
        // f_val 是 b 的剩余部分
        int64 f_val = temp_b;

        if (f_val == 1) {
            // b 是单个质数的幂，无法分解成两个互质的因子
            std::cout << "-1 -1 -1 -1\n";
            return;
        }

        // 现在我们有 df=b, gcd(d,f)=1, d,f > 1
        // 求解 cf - de = a
        // 先用 exgcd 解出 fx + dy = 1
        int64 x, y;
        exgcd(f_val, d_val, x, y); // x, y 是一组特解

        // 根据 x, y 的符号构造 c 和 e
        // 我们知道 x 和 y 必定异号
        // 方案A: 解 f*c - d*e = a, 得 c=a*x, e=-a*y.
        //       要求 c,e > 0, 即 x>0, y<0.
        // 方案B: 解 d*e - f*c = a, 得 e=a*y, c=-a*x.
        //       要求 c,e > 0, 即 y>0, x<0.
        
        // exgcd(f,d,x,y) 返回的 x,y 符号不确定，但总有一种方案可行
        // C++ exgcd 的实现通常使得 |x| <= d, |y| <= f
        // 如果 x 为负，则 y 必定为正
        if (x < 0) {
            // x < 0, y > 0, 使用方案 B
            // c = -a*x, d = f_val, e = a*y, f = d_val
            std::cout << -a * x << " " << f_val << " " << a * y << " " << d_val << "\n";
        } else {
            // x > 0, y < 0, 使用方案 A
            // c = a*x, d = d_val, e = -a*y, f = f_val
            std::cout << a * x << " " << d_val << " " << -a * y << " " << f_val << "\n";
        }
    }
}

int main() {
    // 关掉同步流，让输入输出更快一点喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 预处理
    linear_sieve();

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(\text{MAX\_B} + T \cdot \log b)$
- linear_sieve() 的预处理时间复杂度是 $O(\text{MAX\_B})$ ，其中 $\text{MAX\_B}$ 是 $b$ 的最大值。
- 对于每个查询 $T$ $T$ 次：
  - std::gcd(a, b) 的复杂度是 $O(\log(\min(a,b)))$ 。
  - 使用预处理的 spf 数组分解质因数，复杂度是 $O(\log b)$ 。
  - exgcd 的复杂度是 $O(\log(\min(d,f))) = O(\log b)$ 。
- 所以总时间复杂度由预处理和所有查询的总和决定。
空间复杂度: $O(\text{MAX\_B})$
- 主要的空间开销来自于 spf 数组，用于存储每个数的最小质因子。

知识点总结

这道题真是一次愉快的数论探险呢！我们用到了不少有趣的工具，总结一下吧：

分类讨论思想: 将问题根据 gcd(a, b) 是否为 1 分成两种情况，是解题的关键突破口。简单情况用简单方法，复杂情况再想办法，这让思路清晰很多！
构造法: 对于 gcd(a, b) > 1 的情况，我们直接构造出了一组巧妙的解。构造法在算法竞赛中非常重要，有时候一个简单的设定就能让问题迎刃而解。
线性筛求最小质因子: 为了高效地对 $b$ 进行质因数分解，我们预处理了 spf 数组。线性筛是一种非常高效的筛法，可以在 $O(N)$ 时间内完成任务。
扩展欧几里得算法: 这是解决线性丢番图方程 $ax+by=c$ 的核心武器。本题中，我们用它来求解 $cf-de=a$ ，找到了构造分子 $c, e$ 的方法。
数论性质: 理解 $df=b$ 且 $\gcd(d,f)=1$ 意味着 $b$ 必须有至少两个不同的质因子，是判断无解情况的基础。

希望这篇题解能帮到你，让你也爱上用数学工具解决问题的感觉！下次再一起探险吧，喵~

FractionConstructionProblem - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

Case 1: aaa 和 bbb 不互质 (简单情况喵~) ​

Case 2: aaa 和 bbb 互质 (有点挑战的情况呐) ​

代码实现 ​

复杂度分析 ​

知识点总结 ​