Subtractions
لديك عددان. ما دام كلاهما أكبر من الصفر، تُطبَّق العملية نفسها: اطرح العدد الأصغر من العدد الأكبر. إذا كان العددان متساويين، فاطرح أحدهما من الآخر. مثلًا، عملية واحدة تحوّل الزوج \((4, 17)\) إلى \((4, 13)\)، والزوج \((5, 5)\) إلى \((0, 5)\).
لكل زوج من \(n\) زوجًا \((a_i, b_i)\)، أوجد عدد العمليات التي تُجرى.
القيود:
- \(1 \le n \le 1000\)
- \(1 \le a_i, b_i \le 10^9\)
الإدخال:
- السطر الأول: عدد صحيح \(n\) — عدد الأزواج.
- الأسطر الـ \(n\) التالية: عددان صحيحان \(a_i\) و \(b_i\).
المخرجات:
- لكل زوج، سطر فيه عدد العمليات.
مثال:
الإدخال:
2
4 17
7 987654321المخرجات:
8
141093479الحل
محاكاة العمليات واحدة بعد الأخرى بطيئة جدًا: للزوج \((1, 10^9)\) توجد \(10^9\) عملية، وقد يوجد \(1000\) زوج.
لنفرض أن \(a \ge b\). تطرح العملية \(b\) من \(a\) مرة بعد مرة ما دام \(a \ge b\). يحدث هذا \(\lfloor a / b \rfloor\) مرة متتالية بالضبط، ثم يصبح \(a\) مساويًا لـ \(a \bmod b\). لذلك يمكننا إجراء كل هذه العمليات دفعة واحدة:
- نضيف \(\lfloor a / b \rfloor\) إلى الجواب،
- نستبدل \(a\) بـ \(a \bmod b\)،
- نبدّل العددين إذا لزم حتى يعود الأول هو الأكبر.
هذه بالضبط خطوات خوارزمية إقليدس من درس القاسم المشترك الأكبر، لذلك يحتاج كل زوج إلى \(O(\log(\max(a, b)))\) خطوة فقط.
للزوج \((4, 17)\): \(17 = 4 \cdot 4 + 1\) يعطي \(4\) عمليات والزوج \((4, 1)\)؛ ثم \(4 = 4 \cdot 1 + 0\) يعطي \(4\) عمليات أخرى. الجواب \(8\).
قد يقترب عدد العمليات من \(10^9\)، لذلك نخزّنه في 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";
}
}