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

· · 题解

题目分析

每次变换，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;
}