Romantic

  一道拓展欧几里得的题目，因为是ax + by = 1,所以可以直接用求逆元的方法来求出x,再根据y = (1 - ax) / b求得y。题目要求x是非负的，这在求逆元的过程中已得到了解决。

代码如下:

#include <cstdio> 
#include <iostream> 
#include <cstring> 
#include <cmath> 
#include <algorithm> 
#include <vector>
#include <list>
#include <string>
#include <queue>
#include <assert.h>
#define mst(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e6+5;
ll exgcd(ll a,ll b,ll& x,ll& y)
{    
    ll r;
    if(b==0){    
        x=1;y=0;
        return a;
    }else{
        r=exgcd(b,a%b,y,x);
        y-=x*(a/b);
    }
    return r; 
}
ll solve(ll a,ll b)
{    
    ll x,y;
    ll g=exgcd(a,b,x,y);
    if(1%g)
        return -1;
    x*=1/g;
    if(b<0)        b=-b;
    ll ans=x%b;
    if(ans<=0)
        ans+=b;
    return ans;
}
int main()
{
    ll a,b;
    while(cin>>a>>b)
    {
        ll ans=solve(a,b);
        if(ans==-1)
            cout<<"sorry"<<endl;
        else
        {
            ll ansx=ans;
            ll ansy=(1-a*ansx)/b;
            cout<<ansx<<" "<<ansy<<endl;
        }
    }
    return 0;
}