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

题意

你有一个有序数对 \((x,y)\)，每次你可以选择其中一个数并指定一个整数 \(k\)，然后将你选的那个数除以 \(k\) 下取整，另外一个数乘 \(k\)。你现在想要把 \((a,b)\) 变换成 \((c,d)\) 构造一组在 65 步解决问题的方案，或报告无解。

\(1\le a,b,c,d\le 10^9\)

分析

这题的突破口在于特殊性质 A。不往这方面想基本上就寄飞了。

考虑特殊性质 A：\(ab=cd\)。我们有如下构造方案：\((a,b)\rightarrow (1,ab=cd)\rightarrow (c,d)\)。

考虑更一般的情况。

首先不难发现 \(ab\) 的乘积单调不升，那么 \(ab<cd\) 一定无解。

其次，我们考虑让 \(ab\) 的大小尽可能的接近 \(cd\)。假设我们对第一个数操作，考虑一次操作 \((x,y)\rightarrow(\lfloor\dfrac{x}{k}\rfloor,yk)\)，\(xy\) 的乘积减小了 \(xy-(\lfloor\dfrac{x}{k}\rfloor\cdot k)\cdot y=xy-(x-x\bmod k)\cdot y=(x\bmod k)\cdot y\)。根据经典结论，\(a\bmod b< \dfrac{a}{2}\)，我们想要尽可能的让 \(ab\) 减小的更快，那么我们就想让 \(x\bmod k\) 的值尽可能大，取 \(k=\dfrac{x}{2}+1\) 即可。这样我们每次对 \((x,y)\) 操作 \(k\)，直到 \(cd\le xy<2cd\)。

注意我们无法对 \(1\) 进行任何操作，此时我们需要将这两个数交换后继续做。
而当另一个数为 \(2\) 时，我们只能把这个数除 \(2\)，并把另外的数乘 \(2\)，这样的话 \((1,2)\rightarrow (2,1)\rightarrow \cdots\)，就死循环了。只有当 \(1\cdot 2=2\ge 2cd\) 时会出现这种情况，此时 \(cd=1\)，故当 \(cd=1\) 时只有 \(ab=1\) 时才有解，其他情况无解。

当 \(cd\le ab<2cd\) 时，类比特殊性质 A 的思想，我们有如下构造方案：\((a,b)\rightarrow (ab,1)\rightarrow_{k=cd} (\lfloor\dfrac{ab}{cd}\rfloor=1,cd)\rightarrow (c,d)\)。

至此这道题做完了，使用次数 \(\log ab+3\)，在 65 的次数限制下足以通过。

点击查看代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
#include<ctime>
#include<random>
#include<cassert>
#define IOS ios::sync_with_stdio(false)
#define PY puts("Yes")
#define PN puts("No")
#define PW puts("-1")
#define P0 puts("0")
#define P__ puts("")
#define PU puts("--------------------")
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb emplace_back
#define un using namespace
#define popc __builtin_popcountll
#define all(x) x.begin(),x.end()
#define rep(a,b,c) for(int a=(b);a<=(c);++a)
#define per(a,b,c) for(int a=(b);a>=(c);--a)
#define reprange(a,b,c,d) for(int a=(b);a<=(c);a+=(d))
#define perrange(a,b,c,d) for(int a=(b);a>=(c);a-=(d))
#define graph(i,j,k,l) for(int i=k[j];i;i=l[i].nxt)
#define lowbit(x) (x&-x)
#define lson(x) (x<<1)
#define rson(x) (x<<1|1)
#define mem(x,y) memset(x,y,sizeof x)
//#define double long double
#define int long long
//#define int __int128
using namespace std;
using pii=pair<int,int>;
using i64=long long;
using u64=unsigned long long;
template<typename T>bool greating(T x,T y){return x>y;}
inline int rd(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}return x*f;
}
template<typename T>
inline void write(T x,char ch='\0'){if(x<0){x=-x;putchar('-');}int y=0;char z[40];while(x||!y){z[y++]=x%10+48;x/=10;}while(y--)putchar(z[y]);if(ch!='\0')putchar(ch);
}
bool Mbg;
const int maxn=2e5+5,maxm=4e5+5,inf=0x3f3f3f3f;
const long long llinf=0x3f3f3f3f3f3f3f3f;
int a,b,c,d;
vector<pii>v;
void rev(int &x){x=x==1?2:1;}
inline void solve_the_problem(){a=rd(),b=rd(),c=rd(),d=rd(),v.clear();if(a*b<c*d||(a*b!=1&&c*d==1))return (void)PW;int t=1;while(a*b>=2*c*d){if(a==1)rev(t),swap(a,b);int r=a/2+1;a/=r,b*=r,v.emplace_back(mp(t,r));}if(t==2)swap(a,b);v.emplace_back(mp(2,b));v.emplace_back(mp(1,c*d));v.emplace_back(mp(2,c));write(v.size(),10);for(pii i:v)write(i.fi,32),write(i.se,10);
}
bool Med;
signed main(){
//	freopen(".in","r",stdin);freopen(".out","w",stdout);
//	fprintf(stderr,"%.3lfMB\n",(&Mbg-&Med)/1048576.0);int _=rd();while(_--)solve_the_problem();
}
/**/