Subtractions
You have two numbers. While both of them are greater than zero, the same operation is applied: subtract the smaller number from the larger one. If the numbers are equal, subtract one from the other. For example, one operation changes the pair \((4, 17)\) to \((4, 13)\), and the pair \((5, 5)\) to \((0, 5)\).
For each of \(n\) pairs \((a_i, b_i)\), find how many operations are performed.
Constraints:
- \(1 \le n \le 1000\)
- \(1 \le a_i, b_i \le 10^9\)
Input:
- First line: integer \(n\) — the number of pairs.
- Next \(n\) lines: two integers \(a_i\) and \(b_i\).
Output:
- For each pair, one line with the number of operations.
Example:
Input:
2
4 17
7 987654321
Output:
8
141093479
Solution
Simulating the operations one by one is too slow: for the pair \((1, 10^9)\) there are \(10^9\) operations, and there can be \(1000\) pairs.
Suppose \(a \ge b\). The operation subtracts \(b\) from \(a\) again and again, as long as \(a \ge b\). This happens exactly \(\lfloor a / b \rfloor\) times in a row, and then \(a\) becomes \(a \bmod b\). So we can perform all these operations at once:
- add \(\lfloor a / b \rfloor\) to the answer,
- replace \(a\) with \(a \bmod b\),
- swap the numbers if needed so that the first one is again the larger one.
These are exactly the steps of the Euclidean algorithm from the lesson on the GCD, so each pair needs only \(O(\log(\max(a, b)))\) steps.
For \((4, 17)\): \(17 = 4 \cdot 4 + 1\) gives \(4\) operations and the pair \((4, 1)\); then \(4 = 4 \cdot 1 + 0\) gives \(4\) more operations. The answer is \(8\).
The number of operations can be close to \(10^9\), so we store it in long long.
#include <iostream>
#include <utility>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
long long operations = 0;
while (a > 0 && b > 0) {
if (a < b) {
swap(a, b);
}
// b is subtracted from a exactly a / b times in a row
operations += a / b;
a = a % b;
}
cout << operations << "\n";
}
}