题解：构造满足条件的 (a) 和 (b)

问题分析

题目要求对于给定的正整数 (g) 和 (h)，找到正整数 (a) 和 (b)，满足两个条件：

1. (\gcd(a, b) = g)（最大公约数为 (g)）；
2. (R(a, b) = h)（Edicul 算法的结果为 (h)）。

其中，Edicul 算法 (R(a, b)) 的规则是：

• 若 (a < b)，交换 (a) 和 (b)；
• 若 (a \geq b > 1)，令 (a = \lfloor \frac{a}{b} \rfloor)，重复过程；
• 若 (b = 1)，结果为 (a)。

核心思路

通过构造法直接生成满足条件的 (a) 和 (b)。关键在于利用 Edicul 算法的迭代特性和最大公约数的性质，设计 (a) 和 (b) 的表达式。

构造方法

1. 构造 (b) 的值：

   • 初始令 (b = 1)，不断乘以 (h) 直到 (b > g)（确保后续迭代中 (\lfloor \frac{g}{b} \rfloor = 0)）；
   • 调整 (b) 为 (g) 的倍数（即 (b = k \times g)，保证 (\gcd(a, b)) 至少为 (g)）。

2. 构造 (a) 的值：

   • 令 (a = b \times h + g)。此时 (a) 是 (g) 的倍数（因 (b) 是 (g) 的倍数，(b \times h) 也是 (g) 的倍数，加 (g) 后仍为 (g) 的倍数）。

正确性证明

1. 满足 (\gcd(a, b) = g)

• 设 (b = k \times g)（(k) 为正整数），则 (a = b \times h + g = g \times (k \times h + 1))。
• 因此，(a) 和 (b) 的最大公约数为： [ \gcd(a, b) = \gcd(g \times (k \times h + 1), g \times k) = g \times \gcd(k \times h + 1, k) ]
• 由于 ((k \times h + 1) \mod k = 1)，故 (\gcd(k \times h + 1, k) = 1)，因此 (\gcd(a, b) = g)。

2. 满足 (R(a, b) = h)

• 由 (a = b \times h + g) 和 (b > g)，得 (a > b \times h \geq b)（因 (h \geq 2)），故第一次迭代时 (a) 变为： [ \lfloor \frac{a}{b} \rfloor = \lfloor \frac{b \times h + g}{b} \rfloor = h + \lfloor \frac{g}{b} \rfloor = h \quad (\text{因 } b > g, \lfloor \frac{g}{b} \rfloor = 0) ]
• 此时迭代变为 (R(h, b))。由于 (b) 是通过乘以 (h) 得到的（且 (b \geq h)），后续迭代过程如下：
  • 因 (b \geq h)，交换后为 (R(b, h))；
  • 迭代计算 (\lfloor \frac{b}{h} \rfloor)，最终会逐步缩减至 (1)，剩余的数即为 (h)。

代码实现

#include <cstdio>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int g, h;
        scanf("%d%d", &g, &h);
        long long b = 1;
        // 让 b 成为大于 g 的 h 的幂次
        while (b <= g) {
            b *= h;
        }
        // 调整 b 为 g 的倍数（向上取整）
        b = (b + g - 1) / g * g;
        // 构造 a
        long long a = b * h + g;
        printf("%lld %lld\n", a, b);
    }
    return 0;
}

总结

通过构造 (b) 为大于 (g) 的 (g) 的倍数，且 (a = b \times h + g)，既保证了 (\gcd(a, b) = g)，又利用 Edicul 算法的迭代特性确保了 (R(a, b) = h)。该方法高效且满足数值范围约束（(a, b \leq 10^{18})）。