欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 2669 Romantic

程序员文章站 2024-01-12 09:25:10
...
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll x,ll y,ll& a,ll& b){
    ll ret,tmp;
    if(y==0){
        a=1;
        b=0;
        return x;
    }
    ret=exgcd(y,x%y,a,b);
    tmp=a;
    a=b;
    b=tmp-x/y*b;
    return ret;
}
int main(){
    ll x,y,a,b,d;
    while(scanf("%lld%lld",&x,&y)==2){
        d=exgcd(x,y,a,b);
        while(a<0){
            a+=y;
            b-=x;
        }
        if(d!=1||x*a+y*b!=1)printf("sorry\n");
        else printf("%lld %lld\n",a,b);
    }
    return 0;
}