Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* ax + by =gcd(a,b)
- =>(b%a) * x1 + a*y1 = gcd(a,b)
- =>(b-(b/a)*a)*x1 + a*y1 = gcd(a,b)
- => b*x1 - a*(b/a)*x1 + a*y1 = gcd(a,b)
- => a(y1-(b/a)*x1) + b*x1 = gcd(a,b)
- ----------- ---
- X Y
- */
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- ll gcd(ll a,ll b, ll *x,ll *y)
- {
- if(a==0)
- {
- *x=0;
- *y=1;
- return b;
- }
- ll x1,y1;
- ll ans=gcd(b%a,a,&x1,&y1);
- *x=y1-(b/a)*x1;
- *y=x1;
- return ans;
- }
- int main()
- {
- ll x,y,a,b,c,d;
- while(cin>>a>>b)
- {
- d=gcd(a,b,&x,&y);
- if(a==b)
- x=0,y=1;
- cout<<x<<" "<<y<<" "<<d<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement