বর্ধিত ইউক্লিডীয় অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

এক্সটেন্ডেড ইউক্লিডীয় অ্যালগরিদম হল দুটি সংখ্যার 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