G17 不定方程 扩展欧几里得算法

#include<bits/stdc++.h>
using namespace std;
typedef long long  LL;
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0){d=a;x=1;y=0;}
	else
	{
		exgcd(b,a%b,d,y,x);
		y-=(a/b)*x;
	}
}

int main()
{
	LL A,B,d,X,Y,K;scanf("%lld%lld%lld",&A,&B,&K);
	exgcd(A,B,d,X,Y);
	if(K%d!=0) { printf("no solution!\n");return 0;}
	X=X* (K/d);
	Y=(K- X*A)/B;
	printf("%lld %lld\n",X,Y); 
    return 0;
}