Exponentiation

Exponentiation

CSES easy

احسب \(n\) قيمة من الشكل \(a^b \bmod (10^9 + 7)\). في هذه المسألة \(0^0 = 1\).

القيود:

• \(1 \le n \le 2 \cdot 10^5\)
• \(0 \le a, b \le 10^9\)

الإدخال:

• السطر الأول: عدد صحيح \(n\) — عدد العمليات الحسابية.
• الأسطر الـ \(n\) التالية: عددان صحيحان \(a\) و \(b\).

المخرجات:

• لكل عملية، سطر فيه \(a^b \bmod (10^9 + 7)\).

مثال:

الإدخال:

3
3 4
2 8
123 123

المخرجات:

81
256
921450052

الحل

ضرب \(a\) في نفسه \(b\) مرة يحتاج إلى ما يصل إلى \(10^9\) عملية ضرب لعملية حسابية واحدة، وقد يوجد ما يصل إلى \(2 \cdot 10^5\) عملية حسابية. هذا بطيء جدًا.

نستخدم الأس السريع من درس الحسابيات المعيارية. ينصّف الأسَّ في كل خطوة، لذلك تحتاج كل عملية حسابية إلى \(O(\log b)\) عملية ضرب فقط.

تبقى كل القيم أصغر من \(10^9 + 7\)، لذلك يكون حاصل ضرب قيمتين أصغر من نحو \(10^{18}\) ويتسع في long long. كما تأخذ الدالة modpow باقي قسمة \(a\) على \(10^9 + 7\) قبل أن تضرب.

عندما \(b = 0\) تُرجع الدالة \(1\)، وهذا يعطي أيضًا \(0^0 = 1\).

#include <iostream>
using namespace std;

const long long MOD = 1'000'000'007;

long long modpow(long long a, long long b, long long m) {
    if (b == 0) return 1;

    long long half = modpow(a, b / 2, m);
    long long res = (half * half) % m;

    if (b % 2 == 1) {  // If b is odd
        res = (res * (a % m)) % m;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        cout << modpow(a, b, MOD) << "\n";
    }
}