// 总体思路是先凑出1 2 4 8 16.....直到乘2大于目标数后停止 // 然后用最大值加之前操作的序列,序列为1 2 4 8 ...,所以一定操作次数后一定可以配成目标数字 #include <bits/stdc++.h> using namespace std; const int inf = 0x3f3f3f3f; #define kuaidu ios::sync_with_stdio(false), cin.tie(0), cout.tie(0) #define PII pair<int, int> #define endl '\n' #define PI acos(-1) #define int long long vector<pair<int, PII>> v; signed main() { kuaidu; int T; cin >> T; while (T--) { int x, y; cin >> x >> y; if (x > y) swap(x, y); if (y % x == 0 || x == 1 || y == 1) { cout << 0 << endl; continue; } v.clear(); int res = x * y / __gcd(x, y); //目标数字 multiset<int> mu; int ans = 0; mu.insert(x), mu.insert(y); v.push_back({1, {x, y}}), v.push_back({1, {x, y}}); mu.insert(1), mu.insert(1); //先把两个1插进去 ans += 2; int now = 1; while (now * 2 <= res) { v.push_back({2, {now, now}}), v.push_back({2, {now, now}}); ans += 2; now *= 2; mu.insert(now), mu.insert(now); } now = *mu.rbegin(); while (now < res) { int xu = res - now; auto it = mu.lower_bound(xu); if (now + *it > res) it--; ans++; v.push_back({2, {*it, now}}); mu.insert(now + *it); now = *mu.rbegin(); } cout << ans << endl; for (auto x : v) { cout << x.first << " " << x.second.first << " " << x.second.second << endl; } } }
全部评论
(1) 回帖