C++-এ খুব বড় সংখ্যা a-এর জন্য (a^b)%m বের করা

খুব বড় একটি সংখ্যা a (স্ট্রিং আকারে), এবং পূর্ণসংখ্যা b, m দেওয়া থাকলে, (aᵇ) % m বের করতে হবে।

পদ্ধতি

• প্রথমে a % m বের করুন স্ট্রিং প্রসেসিং দিয়ে।
• তারপর (a%m) কে b বার গুন করে প্রতিবার m দিয়ে মডুলো নিন।
• এটি মডুলার এক্সপোনেনশিয়েশনের সরলীকৃত সংস্করণ।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

unsigned int aModM(string str, unsigned int mod) {
    unsigned int num = 0;
    for (char c : str) {
        num = num * 10 + (c - '0');
        num %= mod;
    }
    return num;
}

unsigned int aPowerBmodM(string &a, unsigned int b, unsigned int m) {
    unsigned int base = aModM(a, m);
    unsigned int result = 1;
    for (unsigned int i = 0; i < b; i++)
        result = (result * base) % m;
    return result;
}

int main() {
    string a = "123456789012345678901234567890123";
    unsigned int b = 3, m = 7;
    cout << aPowerBmodM(a, b, m) << endl;
    return 0;
}

আউটপুট

1