โปรแกรม C++ ใช้ Extended Euclidean Algorithm

Extended Euclidean Algorithm เป็นอีกวิธีหนึ่งในการคำนวณ GCD ของสองจำนวน มีตัวแปรเพิ่มเติมเพื่อคำนวณ ax + by = gcd(a, b) มีประสิทธิภาพมากกว่าสำหรับโปรแกรมคอมพิวเตอร์

อัลกอริทึม

Begin
    ประกาศตัวแปร a, b, x และ y
    gcdExtended(int a, int b, int *x, int *y)
    ถ้า (a == 0)
        *x = 0; *y = 1; return b;
    รับตัวแปรสองตัวเก็บผลลัพธ์
    อัปเดต x และ y โดยใช้ผลลัพธ์จาก recursive call
End

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

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

int gcdExtended(int a, int b, int *x, int *y) {
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}

int main() {
    int x, y;
    int a = 35, b = 15;
    cout<<"gcd "<<gcdExtended(a, b, &x, &y);
    return 0;
}

ผลลัพธ์

gcd 5