【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;
}
Tips
\(10^9 \times 10^9\) 会爆 int，记得开long long。