حساب (a^b)%MOD مع الأسس الكبيرة

في تحدي البرمجة هذا، تتمثل المهمة في حساب قيمة pow( a, b)%MOD، حيث يمكن أن يكون الأس b كبيرًا للغاية. في حين أن طريقة التعقيد الزمني التقليدية للسجل (ب) مناسبة للقيم الأصغر، فإنها تصبح غير عملية عندما تتجاوز b سعة أنواع البيانات الطويلة الطويلة في لغة C.

ومع ذلك، يتضمن النهج الأكثر كفاءة الاستفادة من دالة أويلر المتراكمة، φ(وزارة الدفاع). تنص نظرية أويلر على أن a^φ(MOD)≡1(mod MOD). هذا يعني أنه يمكن تقليل قوة a بشكل كبير إلى a^(b % φ(MOD)).

حساب φ(MOD) هو في حد ذاته مهمة غير تافهة، ولكن يمكن تحقيقه باستخدام طرق تحليل الأعداد الصحيحة . بمجرد الحساب، يمكن استبدال الأس b بـ b % φ(MOD) لتقليل وقت الحساب بشكل كبير.

مزيد من التحسينات

في عام 2008، أثبت شرام أن φ (ب) يمكن الحصول عليها من تحويل فورييه المنفصل لـ gcd(b, i) لأن i تتراوح من 1 إلى b. هذا يلغي الحاجة إلى التحليل الصريح.

بالإضافة إلى ذلك، يمكن استخدام دالة كارمايكل، π(MOD)، للحصول على الإجابة الصحيحة، خاصة عندما يشترك a و MOD في عوامل مشتركة.

تنفيذ الكود

يعمل مقتطف الكود التالي كمثال في لغة C:

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout