Transforming Pairs (USACO Silver 2025 February)

Transforming Pairs (USACO Silver 2025 February)

题意：A: a += b, B: b += a，用这两个操作将(a,b)(a,b)用最小的次数变成(c,d)(c,d)，或者证明不行。

观察：A操作之后a>ba>b，B操作之后b>ab>a。所以我们发现cc和dd的相对大小就决定了最后一次操作是哪个方向的操作，这样我们可以一路从(c,d)(c,d)倒着往回算出整个操作的序列，如果能够到达(a,b)(a,b)，那就有解，否则没有。有点类似GCD的过程。还是正难则反的思想。

具体来说：

  1. 如果c<ac<a或d<bd<b，则−1-1
  2. 不失一般，假设c>dc>d
  3. 如果d=bd = b, 则(c−a)mod  b=0(c-a) \mod b = 0时有解，为“(c−a)/b(c-a)/b + 已经进行的操作次数”，否则−1-1
  4. c←(c−d)mod  dc \leftarrow (c-d) \mod d，然后回到2继续循环
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t;
ll a,b,c,d;
ll ans;
 
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        ans = 0;
 
        while (c >= a && d >= b) {
            if (c == a && d == b)
                break;
            if (c > d) {
                if (d == b) {
                    if ((c-a) % b == 0) {
                        ll tmp = (c-a)/b;
                        ans += tmp;
                        c -= tmp*b;
                        break;
                    } else {
                        ans = -1;
                        break;
                    }
                } else {
                    ans += c / d;
                    c = c % d;
                }
            } else {   // d >= c
                if (c == a) {
                    if ((d-b) % a == 0) {
                        ll tmp = (d-b)/a;
                        ans += tmp;
                        d -= tmp*a;
                        break;
                    } else {
                        ans = -1;
                        break;
                    }
                } else {
                    ans += d / c;
                    d = d % c;
                }
            }
        }
        if (c < a || d < b) {
            ans = -1;
        }
        printf("%lld\n", ans);
    }
 
    return 0;
}