|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
//Extended euclid Algorithm #include <iostream> using namespace std; long long int gcd(long long int a, long long int b) { if(b==0) return a; else return gcd(b,a%b); } int main() { long long int a,b,g,q,temp,t1,t2; while(cin>>a>>b) { //g=gcd(a,b); long long int prevx=1,x=0,y=1,prevy=0; while(b) { q=a/b; t1=x; x=prevx-q*x; prevx=t1; t2=y; y=prevy-q*y; prevy=t2; temp=a; a=b; b=temp%b; } cout<<prevx<<" "<<prevy<<" "<<a<<"\n"; } return 0; } |
Theory:
The pseudo code of the extended euclid algorithm:
xgcd(a,b):
prevx, x = 1, 0; prevy, y = 0, 1
while (b!=0)
{
q = a/b
x = prevx – q*x;
prevx= x;
y = prevy – q*y;
prevy= y;
a = b;
b= a % b;
}
return a, prevx, prevy
[button color=”red” size=”small” link=”https://www.dropbox.com/s/f44huwxpczagql5/extended%20euclid%20algorithm.pdf?dl=0″ target=”blank” ]Download[/button]