Given two numbers $A$,$B$. Let $G$ be the GCD of two numbers. I need to tell the values of $X$ and $Y$ such that
$$ G = X A + Y B $$
How to approach this problem ? Like if we have $A=25$ and $B=45$ then GCD , $G=5$.
So $5 = 2 \times 25 - 1 \times 45$. Hence here $X=2$ and $Y=-1$.
So how to tackle this problem for given $A$ and $B$?
My try :
int a=25;
int b=45;
int s=0;
int old_s=1;
int t=1;
int old_t=0;
int r=b;
int old_r=a;
while(r!=0){
int quotient = old_r / r;
old_r = r;
r = old_r-quotient * r;
old_s = s;
s = old_s - quotient * s;
old_t = t;
t = old_t - quotient * t;
}
cout<< old_s << " " << old_t< cout<< old_r <
cout<< t << " " << s <
Whats wrong with this code ?
No comments:
Post a Comment