โปรแกรม C++ หา GCD ของ a^n และ c โดยที่ a, n และ c มีค่าจาก 1 ถึง 10^9

เราต้องหา GCD ของสองตัวเลข ซึ่งหนึ่งตัวเลขอาจใหญ่ถึง (10^9 ^ 10^9) ซึ่งไม่สามารถเก็บในชนิดข้อมูลอย่าง long หรืออื่นๆ ได้ ดังนั้นถ้าตัวเลขคือ a = 10248585, n = 1000000, b = 12564 ผลลัพธ์ของ GCD(a^n, b) จะเป็น 9

เนื่องจากตัวเลขยาวมาก เราไม่สามารถใช้อัลกอริทึมยุคลิดได้ เราต้องใช้การยกกำลังแบบโมดูลาร์ (modular exponentiation) ด้วยความซับซ้อน O(log n)

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

#include <iostream>
#include <algorithm>
using namespace std;

long long power(long long a, long long n, long long b) {
    long long res = 1;
    a = a % b;
    while (n > 0) {
        if (n & 1)
            res = (res*a) % b;
        n = n>>1;
        a = (a*a) % b;
    }
    return res;
}

long long bigGCD(long long a, long long n, long long b) {
    if (a % b == 0)
        return b;
    long long exp_mod = power(a, n, b);
    return __gcd(exp_mod, b);
}

int main() {
    long long a = 10248585, n = 1000000, b = 12564;
    cout << "GCD value is: " << bigGCD(a, n,b);
}

ผลลัพธ์

GCD value is: 9