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

我们用 $(a, b) \xrightarrow{t, k} (c, d)$ 表示将数对 $(a, b)$ 通过参数为 $k$ 的类型-$t$ 的操作变化成 $(c, d)$ 的过程。如 $(2, 2) \xrightarrow{1, 2} (1, 4)$。

显然一次变化 $(a, b) \xrightarrow{t, k} (a', b')$ 后乘积不会变大，即 $a'b' \le ab$。

所以如果题目给定的 $ab < cd$ 则无解。另一个无解的情况是 $ab\ne 1$ 且 $c = d = 1$，如样例 1。接下来我们将构造地证明除这些情况外都有解。

显然有两个东西：

- $(1, x) \xrightarrow{2, x} (x, 1)$ 以及 $(x, 1) \xrightarrow{1, x} (1, x)$。也就是说 $(1, x),(x,1)$ 可以轻易地相互转换。
- $(a, b) \xrightarrow{1,a} (1,ab)$ 以及 $(cd,1) \xrightarrow{1, k} (c, d)$。也就是说 $(a, b) \rightsquigarrow (c, d)$ 等价于：

$$
\begin{matrix}
&(a, b) \xrightarrow{1,a} (1,ab) \rightsquigarrow (cd,1) \xrightarrow{1, d} (c, d) \\
\text{或 }&(a, b) \xrightarrow{1,a} (1,ab) \rightsquigarrow (1, cd) \xrightarrow{2,c} (c, d)
\end{matrix}
$$

所以我们需要解决 $(1,ab) \rightsquigarrow (cd,1)$ 或 $(1,ab) \rightsquigarrow (1, cd)$。

分类讨论。

- 如果 $\lfloor\frac{ab}{cd}\rfloor = 1$ 那么一步 $(1,ab) \xrightarrow{2,cd} (cd,1)$ 即可。
- 你尝试把它的后一位设成 $1$ 且前一位尽量大。因为这样操作后得到的子问题更容易满足上一个条件。不难发现可以 $(1,ab) \xrightarrow{2, \lfloor \frac{ab}2 \rfloor+1} (\lfloor \frac{ab}2 \rfloor+1,1)$。

重复这样操作，直到情况一发生。不难发现因为你每次有个除以二的操作所以操作总次数是 $\log n$ 的，恰好在 $65$ 内。

代码：

```cpp
signed main() {
	int T;
	cin >> T;
	while (T -- ) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		
		if (a * b < c * d || c * d == 1 && a * b > 1) puts("-1");
		else {
			int pos = 1;
			vector<pair<int, int>> res;
			
			auto work = [&](int t, int k) {
				res.emplace_back(t, k);
				if (t == 1) {
					a /= k;
					b *= k;
				} else {
					a *= k;
					b /= k;
				}
			};
			
			work(1, a);
			while (max(a, b) != c * d) {
				int k = max(c * d, max(a, b) / 2 + 1);
				work(a == 1 ? 2 : 1, k);
			}
			work(a == 1 ? 2 : 1, a == 1 ? c : d);
			
			cout << res.size() << '\n';
			for (auto t : res) cout << t.first << ' ' << t.second << '\n';
		}
	}
	return 0;
}
```

正在渲染内容...