CODEWITHSUNDEEP
c++
user466534
user466534

Reputation:

extended GCD algorithm

i have wrote following algorith for extended GCD algorithm,just dont know how to return triple and could anybody help me?

#include<iostream>
#include<math.h>
using namespace std;
int gcd(int a,int b) {  return (b==0 ?a:gcd(b,a%b));}
long long gcd(long a,long b) { return (b==0 ?a:gcd(b,a%b));}
template<class Int> Int gcd(Int a,Int b) { return (b==0 ?a:gcd(b,a%b));}
template<class Int>
struct Triple
{
  Int d,x,y;
  Triple(Int q,Int w,Int e) :d(q),x(w),y(e)) {}

};

//extended GCD
/* computes d=gcd(a,b)
also x and y such that d=a*x+y*b and return tripls (d,x,y)
                                 */
template<class Int>
Triple <Int> egcd(Int a,Int b) {

   if(!b) return Triple<Int>(a,Int(1),Int(0));
   Triple<int>q=egcd(b,a%b);
   return Triple<Int>(q.d,q.y,q.x-a/b*q.y);
    }

int main(){

     int a=35;
     int b=13;




 return 0;
}

how to finish it using my triple struct constructor?please help me

Upvotes: 0

Views: 1174

Answers (1)

Jiri Kriz
Jiri Kriz

Reputation: 9292

(1) Correct the constructor, it does not compile (remove one bracket):

Triple(Int q,Int w,Int e) : d(q), x(w), y(e) {}

(2) In main() call: 

Triple <int> t = egcd(a, b);
cout << t.d << ", " << t.x << ", " << t.y << endl;

Upvotes: 2

Related Questions