หาตัวเลขหลักสุดท้ายของ a^b สำหรับตัวเลขขนาดใหญ่ใน C++

โจทย์

ได้รับตัวเลข a และ b (อาจใหญ่มาก) ทางเราต้อง หาตัวเลขหลักสุดท้ายของ a^b

ตัวอย่าง

Input: a = 4, b = 124

Output: 6

แนวทางแก้ปัญหา

หลักสุดท้ายของกำลังมีรูปแบบซ้ำทุก 4 ช่วง (Cyclicity):

• หลักสุดท้ายของฐาน (a % 10) กำหนดรูปแบบ
• เลขชี้กำลังใช้ b % 4 (ถ้าเป็น 0 ให้ใช้ 4)
• คำนวณ (last_digit)^exponent % 10

โปรแกรมตัวอย่าง

#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);
    if (len_a == 1 && len_b == 1 && b[0] == '0' && a[0] == '0') return 1;
    if (len_b == 1 && b[0] == '0') return 1;
    if (len_a == 1 && a[0] == '0') return 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