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

· · 题解

P11063 题解

思路

如果 k \mid x，则 x \times k = \lfloor\frac{x}{k}\rfloor \times y \cdot k，如果 k \mid y，则 x \times k = x \cdot k \times \lfloor\frac{y}{k}\rfloor。

考虑 a \times b = c \times d 的情况。令 k=a 进行类型 1 的变换得到 (1,b \times a)，令 k=c 进行类型 2 的变换得到 (c,\frac{b \times a}{c})，因为 a \times b = c \times d，所以 d=\frac{b \times a}{c}。

if (a*b==d*c) {
    printf("2\n");
    printf("%lld %lld\n",1,a);
    printf("%lld %lld\n",2,c);
    continue;
}

这样一来，便可以获得子任务 2 的部分分。

接下来考虑 a \times b \neq c \times d 的情况，若 k 不是 x 的因数，那么进行类型 1 变换的时候，a \times b 的值一定会减小，同理，若 k 不是 y 的因数，那么进行类型 2 变换的时候，a \times b 的值也一定会减小。

因此得出一个结论，若 a \times b < c \times d，则无解。

然后就要考虑如何将 a \times b 经过若干次变换之后得到 c \times d 了。

为了方便，先进行类型 2，a \leftarrow a \times b，则 b \leftarrow 1。

由于向下取整，那么进行变换后 a 或 b 会变得更小一些，拿类型 1 作为例子，取一个 k 进行变换，a \times b 的值会变为 \lfloor\frac{a}{k}\rfloor \times k \times b，发现 \lfloor\frac{a}{k}\rfloor \times k 的值就是 \max\limits_{k \le t \le a, \space k \mid t} t，即最大的不超过 a 的是 k 的倍数的数，那么，变换后的 a \times b 的值就是 t \times b，即减少了 b \times (a-t)，前面我们将 b 设为 1 了，所以变换后 a \times b - c \times d 的值会减小 a-t。

不难证明，对于任意 \lfloor\frac{a}{2}\rfloor+1 \le k \le t \le a，k \mid t，t 的值是唯一的。

所以，每一次，我们取 k = \max(\lfloor\frac{a}{2}\rfloor+1, b - (a \times b - c \times d))，那么 a \times b - c \times d 的值会减小 a - k，然后 a \leftarrow \lfloor\frac{a}{k}\rfloor, \space b \leftarrow b \times k，然后 a 会变成 1，然后 a,b 反着继续做，依此类推。

代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define endl '\n'
#define FRR(file) freopen(file,"r",stdin)
#define FRW(file) freopen(file,"w",stdout)
#define _rep(i,a,b) for (int i=(a);i<=(b);++i)
#define _reps(i,a,b,c) for (int i=(a);i<=(b);c)
#define _rrep(i,a,b) for (int i=(a);i>=(b);--i)
#define _rreps(i,a,b,c) for (int i=(a);i>=(b);c)
#define _iter(i,a) for (auto i=a.begin();i!=a.end();++i)
#define _graph(i,u) for (int i=h[u];~i;i=ne[i])
#define rint register int
#define LL long long
typedef pair<int,int> pii;

int T;
int a,b,c,d;

vector<pii> ans;

signed main() {
    scanf("%lld",&T);
    while (T--) {
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        if (a*b==d*c) {
            printf("2\n");
            printf("%lld %lld\n",1,a);
            printf("%lld %lld\n",2,c);
            continue;
        } else if (a==c && b==d) {
            puts("0");
            continue;
        } else if (a*b<c*d) {
            puts("-1");
            continue;
        }
        ans.clear();
        ans.push_back({2,b});
        a*=b,b/=b;
        int bias=a*b-c*d;
        bool ok=true;
        while (bias) {
            // cout<<bias<<" "<<a-bias<<" "<<b-bias<<endl;
            if (a==1) {
                int k=b/2+1;
                k=max(k,b-bias);
                ans.push_back({2,k});
                if (b-k==0) {
                    ok=false;
                    break;
                }
                bias-=b-k;
                b/=k,a*=k;
            } else {
                int k=a/2+1;
                k=max(k,a-bias);
                ans.push_back({1,k});
                if (a-k==0) {
                    ok=false;
                    break;
                }
                bias-=a-k;
                a/=k,b*=k;
            }
        }
        if (!ok) {
            puts("-1");
            continue;
        }
        ans.push_back({1,a});
        ans.push_back({2,c});
        printf("%lld\n",ans.size());
        _iter(it,ans) printf("%lld %lld\n",it->first,it->second);
    }
    return 0;
}

/*
1
80 43 52 64
*/

/*
1
987654321 123456789 313814116 388538872
*/