Solution 「Jason-1」数对变换

鲜花：怎么 T2 比这题还难啊。

这篇文章主要讲解如何得出正解的思维过程。

观察题目，发现不超过 $65$ 次操作非常的具有提示性。结合 $10^9$ 的数据范围，有这些可能：

1. 进行 $\log10^9$ 次行动，每次行动花费代价为 $2$。
2. 进行 $\log10^{18}$ 次操作。

发现题目中的操作有带下取整，如果不带，那么无论怎么操作 $(x,y)$ 其 $x\cdot y$ 都是定值。有带下取整时，发现操作后的两数的积一定是要小于等于操作前两数的积的。这样，若是有 $a\cdot b<c\cdot d$ 则直接无解。

发现如果一直对 $(a,b)$ 操作十分困难，因为每次操作都涉及到两个数字，那么如果能只对一个数字操作呢？考虑变成 $(a\cdot b,1)$（只需要执行操作把右边的 $b$ 除到左边去），这样只需要将其转化为 $(c\cdot d,1)$ 即可。

再考虑到上文对操作数量的分析，可以得出结论：通过 $\log10^{18}$ 次操作将 $a\cdot b$ 变成 $c\cdot d$。

记 $s=a\cdot b,t=c\cdot d$。发现如果有 $t\le s<2t$，则可以直接 $(s,1)\to(1,t)$，只需除以 $t$ 即可。

那么如何每次将 $s$ 缩小一半呢？发现下取整的性质，如果有 $x>\frac{s}{2}$，则 $\lfloor\frac{s}{x}\rfloor=1$。那么我们想到每次将 $s$ 除以 $\lfloor\frac{s}{2}\rfloor+1$，就能保证其缩小一半了！这样直到 $t\le s<2t$ 再进行上文的操作即可。

需要注意的是每次操作会把 $(x,y)$ 的两项互换，所以还需记录 $s$ 的位置。同时当 $s=2$ 时上述的操作就无法进行了（样例一第二组）。

代码：

int a,b,x,y;
il void work(){
	a=read(),b=read(),x=read(),y=read();
	int s=a*b,t=x*y;
	if(s<t){puts("-1");return;}
	vector<pii>op;
	op.eb(mp(2,b));
	int val=1,zero=2,c=0;
	while(s>=t*2){
		op.eb(mp(val,s/2+1));
		s=s/(s/2+1)*(s/2+1);
		swap(val,zero); 
		c++;
		if(c>=66){puts("-1");return;}
	}
	op.eb(mp(val,t));swap(val,zero);
	if(val==1)op.eb(mp(val,y));
	else op.eb(mp(val,x));
	
	printf("%lld\n",op.size());
	for(pii p:op){
		printf("%lld %lld\n",p.first,p.second);
	}
}