หา (a^b)%m โดยที่ 'a' เป็นตัวเลขใหญ่มากใน C++

ในบทช่วยสอนนี้ เราจะแก้สมการ (a^b)%m ที่ a เป็นตัวเลขใหญ่มาก

สมการ (a^b)%m = (a%m) * (a%m) ... b ครั้ง เราสามารถแก้ปัญหาได้โดยการหาค่า a%m แล้วคูณมัน b ครั้ง

มาดูขั้นตอนในการแก้ปัญหา

• เริ่มต้นตัวเลข a, b, และ m
• เขียนฟังก์ชันเพื่อหา a%m
  • เริ่มต้นตัวเลขด้วย 0
  • วนลูปผ่านตัวเลขในรูปแบบสตริง
  • บวกหลักสุดท้ายเข้าไปในตัวเลข
  • อัปเดตตัวเลขด้วยตัวเลข modulo m
• ได้ค่าของ a%m
• เขียนลูปที่วน b ครั้ง
  • คูณ a%m และ modulo ผลลัพธ์กับ m
• พิมพ์ผลลัพธ์

ตัวอย่างโค้ด

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

unsigned int aModm(string str, unsigned int mod) {
    unsigned int number = 0;
    for (unsigned int i = 0; i < str.length(); i++) {
        number = number * 10 + (str[i] - '0');
        number %= mod;
    }
    return number;
}

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

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

ผลลัพธ์

ถ้าคุณรันโปรแกรมด้านบน คุณจะได้ผลลัพธ์ดังนี้

1

สรุป

หากคุณมีคำถามในบทช่วยสอนนี้ ให้ระบุในส่วนความคิดเห็น