自动搬运

查看原文

来自洛谷，原作者为

	InformationEntropy We must know,and we will know!

搬运于2025-08-24 23:03:56，当前版本为作者最后更新于2024-09-16 21:31:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目分析

每次变换，$a,b$ 都在变化，难以把控，故考虑把 $a,b$ 捆绑在一起。注意到只要变换到 $a\cdot b = c\cdot d$ 则只需两步便可结束：

$$(a,b)\rightarrow(\gcd(a,c),\dfrac{b\cdot a}{\gcd(a,c)})\rightarrow(c,d) $$

故只需考虑 $a\cdot b$ 的变化即可。

又有 $\forall a,b,k \in \N,k\ne0,$

$$\left\lfloor\dfrac{a}{k}\right\rfloor\cdot b\cdot k \le a\cdot b $$

当且仅当 $k \mid a$ 时取等。

这意味着，经过若干次操作后，数对中两数的积不会增加，若初始 $a\cdot b <c\cdot d$ 直接无解。

考虑 $a\cdot b$ 在进行操作 $(1,k)$ 前后的变化量：

$$a=tk+r$$ $$a\cdot b-\left\lfloor\dfrac{a}{k}\right\rfloor\cdot k\cdot b=a\cdot b-t\cdot k\cdot b=a\cdot r $$

（操作 2 同理。）

由于 $a,b$ 动态变化，考虑始终将其一固定（即 $a,b$ 交替变化为固定值），不妨令定值为 1，则每次变换， $a\cdot b$ 减少 $r$，考虑从最后一次操作逆推，$r=a\cdot b-c\cdot d$ 时结束操作，此时可令 $k=c\cdot d$，则 $a\cdot b<2\cdot c\cdot d$ 时满足上述条件。

对于 $a\cdot b \ge c\cdot d\cdot2$，控制 $a,b$ 之一为 1，另一个除以比它的一半大一点的数，可实现 $a\cdot b$ 以 2 的幂次递缩，保证复杂度为 $\operatorname{O}(\log n)$，直到 $a\cdot b<2\cdot c\cdot d$，化归为上一种情况。

最终变化：

$$(a,b)\rightarrow(ab,1)\rightarrow(1,\left\lfloor\dfrac{ab}{2}\right\rfloor+1)\dots\rightarrow(1,cd)/(cd,1)\rightarrow(c,d) $$

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
template<class T>inline void read(T &x){
	x=0;
	int 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);
	if(f) x=-x;
}
ll gcd(ll a,ll b){
	if(a%b == 0){
		return b;
	}
	return gcd(b,a%b);
}
struct node{
	ll op,k;
}ans[65];
int main(){
	int T;
	read(T);
	ll a,b,c,d;
	for(int i=1; i<=T; i++){
		read(a);
		read(b);
		read(c);
		read(d);
		ll k = a*b-c*d;
		if(c*d == 1 && a*b != 1){
			cout << -1 << endl;
			continue;
		}
		if(a==c && b==d){
			cout << 0 << endl;
			continue;
		}//这两个特判不要忘
		if(k == 0){
			cout << 2 << endl;
			cout << 1 << " " << a/gcd(a,c) << endl;
			cout << 2 << " " << c/gcd(a,c) << endl;
		}else if(k < 0){
			cout << -1 << endl;
		}else{
			ll u=a*b,v=c*d;
			int cnt = 0;
			ans[++cnt].op = 2;
			ans[cnt].k = b;
			int op = 0;
			while(u >= (v<<1)){
				ans[++cnt].op = op+1;
				ans[cnt].k = (u>>1)+1;
				u = (u>>1)+1;
				op ^= 1;
			}//a,b辗转变为1
			if(op == 1){
				ans[++cnt].op = 2;
				ans[cnt].k = u;
			}
			ans[++cnt].op = 1;
			ans[cnt].k = v;
			ans[++cnt].op = 2;
			ans[cnt].k = c;
			cout << cnt << endl;
			for(int j=1; j<=cnt; j++){
				cout << ans[j].op << " " << ans[j].k << endl;
			}
		}
	}
	return 0;
}