问题:形如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;
}
Comments | NOTHING