C++-এ বড় সংখ্যার জন্য a^b-এর শেষ ডিজিট বের করুন

দুটি বড় সংখ্যা a এবং b (স্ট্রিং আকারে) দেওয়া আছে। a^b-এর শেষ ডিজিট বের করতে হবে।

উদাহরণ

ইনপুট: a = "559", b = "4532" → আউটপুট: 1

গাণিতিক পর্যবেক্ষণ

1. কোনো সংখ্যার ঘাতের শেষ ডিজিট ৪-য় পিরিয়ডিক (সাইকেল দৈর্ঘ্য ৪)।
2. উদাহরণ: ২-এর ঘাতগুলো: ২, ৪, ৮, ৬, ২, ৪, ৮, ৬...
3. সুতরাং শুধু b % 4 জানলেই চলে।
4. এছাড়া বেস a-এর শুধু শেষ ডিজিটই মোনেই।

অ্যালগরিদম

1. base = a[last_digit] - '0'
2. exp = b % 4 (স্ট্রিং মডুলো ফাংশন দিয়ে)।
3. যদি exp == 0 হয় তবে exp = 4 (কারণ ৪র্থ ঘাতই সাইকেলের শেষ)।
4. result = (base^exp) % 10 রিটার্ন করুন।

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

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

int calcModulus(char b[], int a) {
    int mod = 0;
    for (int i = 0; i < strlen(b); i++)
        mod = (mod * 10 + b[i] - '0') % a;
    return mod;
}

int calcLastDigitInExpo(char a[], char b[]) {
    int len_a = strlen(a), len_b = strlen(b);
    // Edge cases
    if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0') return 1; // 0^0 = 1 (convention)
    if (len_b == 1 && b[0] == '0') return 1; // a^0 = 1
    if (len_a == 1 && a[0] == '0') return 0; // 0^b = 0
    int exponent = (calcModulus(b, 4) == 0) ? 4 : calcModulus(b, 4);
    int base = a[len_a - 1] - '0';
    int result = pow(base, exponent);
    return result % 10;
}

int main() {
    char a[] = "559", b[] = "4532";
    cout << "The last digit in of the value is " << calcLastDigitInExpo(a, b);
    return 0;
}

আউটপুট

The last digit in of the value is 1

ব্যাখ্যা

• calcModulus স্ট্রিং নেয়ার মডুলো বের করে (ডিজিট বাই ডিজিট) — বড় সংখ্যা হ্যান্ডেল করে।
• base = 9 (৫৫৯-এর শেষ ডিজিট), exp = 4532 % 4 = 0 → 4।
• 9⁴ = 6561 → শেষ ডিজিট 1।
• এজ কেস: 0^0 কনভেনশনালি ১ মाना হয়।

লুক-আপ টেবিল (ও(১) কনস্ট্যান্ট)

int lastDigitCycle[10][4] = {
    {0,0,0,0}, {1,1,1,1}, {2,4,8,6}, {3,9,7,1}, {4,6,4,6},
    {5,5,5,5}, {6,6,6,6}, {7,9,3,1}, {8,4,2,6}, {9,1,9,1}
};
// ans = lastDigitCycle[base][(exp-1)%4];