题解：P11063 【MX-X4-T3】「Jason-1」数对变换

naughty-naught / 2024-10-15 / 原文

Problem Link

【MX-X4-T3】「Jason-1」数对变换

题外话

场上把贪心注重在一个奇怪地方了，导致交的时候已经有 $9$ 个人 $\textcolor{green}{AC}$ 了（哭）。

题意简述

对于数对 $(x,y)$，你可以执行以下两种变换：

类型 1：取 $1 \le k \le x$，令 $(x,y) \gets (\lfloor \frac{x}{k} \rfloor, y \cdot k)$。
类型 2：取 $1 \le k \le y$，令 $(x,y) \gets (x \cdot k, \lfloor \frac{y}{k} \rfloor)$。

显然，变换后的数对仍然是正整数数对。

给出两组正整数数对 $(a, b)$ 与 $(c, d)$，你需要执行不超过 $\bm{65}$ 次变换将 $(a, b)$ 变为 $(c, d)$，或者报告无解。注意：你不需要最小化执行变换的次数。

Solution

不难发现，当 $\dfrac{a}{c}=\dfrac{d}{b}$ 即 $a \times b = c \times d$ 时，最多两步操作即可完成数对变换，我们称 $a \times b = c \times d$ 的状态为“最终态”。

手玩一些数据之后，显然操作 $1$ 和操作 $2$ 本质一样，同时操作 $1$ 与操作 $2$ 必然是交替进行（因为多次操作 $1$ 亦或是多次 $2$ 都可以并为一次操作）。

因为操作 $1$ 和操作 $2$ 本质无差别，故后文将以“操作”代替操作 $1$ 或操作 $2$，同时默认操作是类型 $1$。

推论：每次非进入最终态的操作必定化为使数对 $(a, b)$ 变成形如 $(x, 1)$ 的形式，且操作的 $k$ 值为 $a/2+1$ 或 $b/2+1$。

证明

首先，若一次操作之后进入最终态，本轮操作就大部分解决了，所以我们要尽量进入最终态，也就是说 $a \times b$ 要尽量接近 $c \times d$。

思考一次操作能为我们带来多大的贡献。

假设对数对 $(a, b)$ 进行操作，取 $k$ 值为 $k$，设：

\[ a = p \times k + q (0 \le q < k)。 \]

则操作结束后数对 $(a, b)$ 将变成数对 $(p, b \times k)$，数对之积减少了 $b \times q$。

$b$ 为定值，则要使 $q$ 尽量大。

发现 $q$ 在 $k = a/2+1$ 取最大值，此时 $p$ 为 $1$。

证毕。

之后的思路就清晰起来了：每次对于数对 $(a, 1)$，若无法使其一次进入最终态（即 $a \ge (2 \times c \times d)$），就进行操作直到进入最终态。

其他疑问见代码。

代码

// written by Naught
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
// #define int long long
#define Maxn 105
#define p2(x) ((x)*(x))
#define fo(i, l, r) for (int i = l; i <= r; ++i)
#define fr(i, r, l) for (int i = l; i >= r; --i)
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21], *p1 = buf, *p2 = buf;
inline int read(int x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
// void train() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);}

struct ope
{
    int op;
    ll k;
}ans[Maxn];
ll cnt;

void print()
{
    printf("%lld\n", cnt);
    fo(i, 1, cnt) printf("%d %lld\n", ans[i].op, ans[i].k);
}

int main()
{
    int _ = read();
    while(_--)
    {
        ll x = lread(), y = lread(), c = lread(), d = lread(); cnt = 0;
        if(x == c && y == d) {puts("0");continue;}
        if(x * y < c*d ) {puts("-1");continue;}
        int tmp = 2;
        ans[++cnt] = {tmp, y}; x *= y, y = 1, tmp = 3-tmp;
        while(x*y >= 2*c*d && cnt <= 63)
        {
            ll k = x*y/2+1;
            ans[++cnt] = {tmp, k};
            if(tmp == 2) y /= k, x *= k;
            else x /= k, y *= k;
            tmp = 3-tmp;
        }
        if(cnt == 64 && x*y != c*d) {puts("-1"); continue;}
        ans[++cnt] = {tmp, c*d}; tmp = 3-tmp;
        ans[++cnt] = {tmp, tmp == 1? d: c};
        print();
    }
    return 0;
}