【题解】P15632 [2019 KAIST RUN Spring] A Plus Equals B

BpbjsGreen · 2026-03-07 15:38:58 · 题解

从直观来看，我们当然更想要操作一个数的时候，另一个数不变。题面中符合这种要求的操作只有 A+=A 和 B+=B，这等价于将 A 或 B 变成原来的两倍。于是想到考察奇偶性。

首先，A=kp, B=kq 的情况与 A=p,B=q 的情况是等价的。

其次，A=2p, B=q 可以由操作变为 A=p,B=q 的等价情况。因为我们可以 B+=B 使 B=2q，然后 A=2p, B=2q 的情况与 A=p,B=q 的情况是等价的。

也就是说，我们多了一种与“A/=2”等价的操作。

于是我们有了一个做法：

while (a != b)
{
  // Step 1
    while (a % 2 == 0) a /= 2; 
    while (b % 2 == 0) b /= 2;
  // Step 2
    if (a < b) b += a;
    if (b < a) a += b;
}

第一步将 A,B 中的偶数变为奇数。不妨设第二步开始时 A<B，则第二步将较小的 B 加到 A 上，使 A 变成偶数，这样新的一轮操作开始时 A 一定比原来的更小。如此反复，A+B 会变得越来越小，最后有 A=B=1。

从直观上来看，砍半的次数还是比较多的，所以操作次数应该不会多于 5000。但是我并没有证明出操作次数不超过 5000，希望以后可以得到证明。以下我给出了一个操作次数不超过 7200 的证明。

:::info[操作次数不超过 7200 的证明] 以下均只考虑 A,B 等价的最简形式。设 A < B。

考察 A,B 的乘积 AB，我们证明：不多于 2\lfloor\log_2B\rfloor+1 步操作就可以使乘积 AB 减少至少一半。记每一次使乘积减少至少一半的操作为“比比”。

若 A, B 其中之一为偶数，则使用 A/=2 或 B/=2 就可以使乘积减少一半。

若 A,B 都是奇数，设 B-A=C，则 2 次操作

会使 C\to\frac{C}{2}。显然在 2\lfloor\log_2C\rfloor 次操作之内 C 一定会变为一个奇数。当 C 为奇数时，B=A+C 为偶数，此时使用 B/=2，乘积就比初始时减少了至少一半。

又因为 C<B，故 2\lfloor\log_2C\rfloor+1\leq2\lfloor\log_2B\rfloor+1。

回到原题。第 1 次“比比”开始时 AB 小于 10^{36}，此后每一步的乘积 AB 都减少至少一半，所以第 i 次“比比”开始时 AB 小于 10^{36}/2^{i-1}，此时 B<\sqrt{AB}<\sqrt{10^{36}/2^{i-1}}。故操作的次数小于

:::

以下是代码。

signed main()
{
    scanf("%lld%lld", &a, &b);
    while (a != b)
    {
        while (a % 2 == 0)
            s.push_back(4), a >>= 1;
        while (b % 2 == 0)
            s.push_back(1), b >>= 1;
        if (a < b)
            s.push_back(3), b += a;
        if (b < a)
            s.push_back(2), a += b;
    }
    printf("%lld\n", s.size());
    for (auto i : s)
    {
        if (i == 1)
            puts("A+=A");
        else if (i == 2)
            puts("A+=B");
        else if (i == 3)
            puts("B+=A");
        else
            puts("B+=B");
    }
    return 0;
}