Advertisement
Farjana_akter

Untitled

Mar 30th, 2020
129
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.69 KB | None | 0 0
  1. /* ax + by =gcd(a,b)
  2. =>(b%a) * x1 + a*y1 = gcd(a,b)
  3. =>(b-(b/a)*a)*x1 + a*y1 = gcd(a,b)
  4. => b*x1 - a*(b/a)*x1 + a*y1 = gcd(a,b)
  5. => a(y1-(b/a)*x1) + b*x1 = gcd(a,b)
  6. ----------- ---
  7. X Y
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. typedef long long int ll;
  13.  
  14.  
  15.  
  16. ll gcd(ll a,ll b, ll *x,ll *y)
  17. {
  18. if(a==0)
  19. {
  20. *x=0;
  21. *y=1;
  22. return b;
  23. }
  24. ll x1,y1;
  25. ll ans=gcd(b%a,a,&x1,&y1);
  26.  
  27. *x=y1-(b/a)*x1;
  28. *y=x1;
  29. return ans;
  30. }
  31.  
  32.  
  33. int main()
  34. {
  35. ll x,y,a,b,c,d;
  36. while(cin>>a>>b)
  37. {
  38. d=gcd(a,b,&x,&y);
  39. if(a==b)
  40. x=0,y=1;
  41. cout<<x<<" "<<y<<" "<<d<<endl;
  42. }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement