问题:形如a*x+b*y=c(a,b均不为0)的方程,a,b,c都是整数,求(x,y)整数解。

判断是否有解:
整数二元一次方程有解的充要条件是gcd(a,b)|c。如果不能整除则无解。

hdu2669
exgcd模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y);//求出a,b的最大公约数
    ll tmp=x;x=y;y=tmp-a/b*y;
    return gcd;
}
ll cal(ll a,ll b,ll c)
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);
    if(c%gcd!=0)return -1;//代表无解
    x*=c/gcd;b/=gcd;
    ll ansx=x%abs(b);
    if(ansx<=0)ansx+=b;
    return ansx;
}
int main()
{
    ios::sync_with_stdio(false);
    ll a,b,ansx;
    while(cin>>a>>b)
    {
        ansx=cal(a,b,1);
        if(ansx==-1)printf("sorry\n");
        else printf("%lld %lld\n",ansx,(1-ansx*a)/b);
    }
    return 0;
}