확장 유클리드 알고리즘은 두 숫자의 GCD를 계산하는 또 다른 방법입니다. ax + by =gcd(a, b)를 계산하기 위한 추가 변수가 있습니다. 컴퓨터 프로그램에서 사용하는 것이 더 효율적입니다.
알고리즘
Begin Declare variable a, b, x and y gcdExtended(int a, int b, int *x, int *y) if (a == 0) *x = 0; *y = 1; return b; Take two variables to store the result Update x and y using results of 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