الأسس

الأسس

الأولمبياد الوطني للبرمجة 2026 - المسابقة التجريبية

الزمن المحدد: 1 ثانية
الذاكرة المحددة: 256 ميجابايت

أُعطيت ثلاثة أعداد صحيحة \(A\) و\(B\) و\(M\). احسب: \(A^B \bmod M\).

المدخلات

تتكون المدخلات من ثلاثة أعداد صحيحة \(A\) و\(B\) و\(M\)، حيث \((0 \le A,B \le 10^6)\) و\((1 \le M \le 10^9)\).

المخرجات

اطبع قيمة \(A^B \bmod M\).

التقييم

المجموعة	القيود	النقاط
\(1\)	\(A \equiv 0 \pmod M\)	\(13\)
\(2\)	\(A \equiv 1 \pmod M\)	\(11\)
\(3\)	\(A \equiv M-1 \pmod M\)	\(35\)
\(4\)	لا توجد قيود إضافية	\(41\)

أمثلة

المدخلات

2 3 10

المخرجات

8

المدخلات

10 3 5

المخرجات

0

المدخلات

7 100 6

المخرجات

1

الحل

استخدم الأس السريع. ما دام \(B>0\)، ربّع الأساس في كل خطوة، وإذا كان البت الحالي من \(B\) يساوي \(1\) فاضرب الأساس في الإجابة. خذ باقي القسمة على \(M\) مباشرة بعد كل عملية. التعقيد الزمني \(O(\log B)\) والذاكرة \(O(1)\).

#include <iostream>
using namespace std;

int main() {
    long long a, b, m;
    cin >> a >> b >> m;

    a %= m;
    long long answer = 1 % m;

    while (b > 0) {
        if (b % 2 == 1) {
            answer = answer * a % m;
        }
        a = a * a % m;
        b /= 2;
    }

    cout << answer << '\n';
}