D题 50%求助

参考了题解的思路，算gcd的2次幂倍，然后把lcm凑出来。

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

typedef long long ll;
#define For(i, a, b) for (int i = (a); i <= (b); i++)
#define FOR(i, a, b) for (int i = (a); i >= (b); i--)

const ll maxn = 1e18;

ll gcd(ll x, ll y) {
    return (y == 0) ? x : gcd(y, x % y);
}

ll v[400];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int tc;
    cin >> tc;
    while (tc--) {
        ll x, y;
        cin >> x >> y;
        ll lcm = x * y / gcd(x, y);
        ll g0 = gcd(x, y);
        ll s = lcm / g0;
        if (x == lcm || y == lcm) {
            cout << 0 << endl;
            continue;
        }
        vector<array<ll, 3>> ans;
        ans.push_back({1ll, x, y});
        ans.push_back({1ll, x, y});
        int pos = -1;
        ll sum = 0;
        for (int i = 0; i <= 63; i++) {
            v[i] = g0 * (1ll << i);
            if (v[i] > maxn) break;
            ans.push_back({2ll, g0 * (1ll << i), g0 * (1ll << i)});
            sum += v[i];
            if (sum > lcm) {
                pos = i;
                break;
            }
            ans.push_back({2ll, g0 * (1ll << i), g0 * (1ll << i)});
            sum += v[i];
        }
        int top = pos;
        while (v[top] < lcm) {
            while (v[top] + v[pos] > lcm) pos--;
            ans.push_back({2ll, v[top], v[pos]});
            ++top;
            v[top] = v[top - 1] + v[pos];
        }
        cout << ans.size() << endl;
        for (auto [u, v, w] : ans)
            cout << u << " " << v << " " << w << endl;
    }
    return 0;
}