C++-এ ৫-ডিজিট সংখ্যায় ৫ ঘাতের শেষ ৫ ডিজিট বের করুন

একটি ৫-ডিজিট সংখ্যা N দেওয়া আছে। N⁵ (N-এর ৫ ঘাত) এর শেষ ৫ ডিজিট বের করতে হবে।

উদাহরণ

ইনপুট: N = 12345 → আউটপুট: 65625

অ্যালগরিদম: মডুলার এক্সপোনেনশিয়েশন

পুরো N⁵ ক্যালকুলেট করলে ওভারফ্লো হয়ে যাবে। বরং প্রতিটি গুণনের পর % 100000 নিন — শুধু শেষ ৫ ডিজিট রাখবে।

1. result = 1
2. ৫ বার লুপ: result = (result * N) % 100000
3. ফাইনাল result = শেষ ৫ ডিজিট।

C++ প্রোগ্রাম

#include <iostream>
using namespace std;

int lastFiveDigits(int n) {
    int result = 1;
    for (int i = 0; i < 5; i++) {
        result *= n;
        result %= 100000;
    }
    cout << "The last five digits of " << n << " raised to the power 5 are " << result;
    return result;
}

int main() {
    int n = 12345;
    lastFiveDigits(n);
    return 0;
}

আউটপুট

The last five digits of 12345 raised to the power 5 are 65625

ব্যাখ্যা

• (a × b) % m = ((a % m) × (b % m)) % m — মডুলার গুণের বৈশিষ্ট্য।
• প্রতিটি স্টেপে result ছোট থাকে → ওভারফ্লো হয় না।
• জেনেরিক ফাংশন: modPow(base, exp, mod) দিয়ে যেকোনো ঘাতের মডুলো বের করা যায়।

জেনেরিক মডুলার এক্সপোনেনশিয়েশন (O(log exp))

long long modPow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
// ব্যবহার: modPow(n, 5, 100000)

কমপ্লেক্সিটি

• সিম্পল লুপ: O(exp) = O(5) = O(1)।
• ফাস্ট এক্সপোনেনশিয়েশন: O(log exp)।
• স্পেস: O(1)।