对于不定整数方程pa+qb=c，若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。

上面已经列出找一个
整数解的方法，在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，
/*p * a+q * b = Gcd(a, b)的其他整数解满足：

p = p0 + a/Gcd(a, b) * t

q = q0 - b/Gcd(a, b) * t(其中t为任意
整数)

至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可

在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是

得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整数解满足：

p = p1 + b/Gcd(a, b) * t

q = q1 - a/Gcd(a, b) * t(其中t为任意
整数)

p 、q就是p * a+q * b = c的所有
整数解。

就是运用扩展欧几里德求出 的 p，q给的是最小的那一组 有可能是负的 而题目 明显要求了 x不能为负，所以要利用上述性质 来求出最小 正解

#include<iostream>

#include<cstdio>

#include<list>

#include<algorithm>

#include<cstring>

#include<string>

#include<queue>

#include<stack>

#include<map>

#include<vector>

#include<cmath>

#include<memory.h>

#include<set>

#define ll long long

#define LL __int64

#define eps 1e-8

const ll INF=9999999999999;

#define M 400000100

#define inf 0xfffffff

using namespace std;

//vector<pair<int,int> > G;

//typedef pair<int,int> P;

//vector<pair<int,int>> ::iterator iter;

//

//map<ll,int>mp;

//map<ll,int>::iterator p;

//

//vector<int>G[30012];

LL extgcd(LL a,LL &x,LL b,LL &y)

{

	if(b==0)

	{

		x=1;

		y=0;

		return a;

	}

	LL r=extgcd(b,x,a%b,y);

	LL t=x;

	x=y;

	y=t-a/b*y;

	return r;

}

int main(void)

{

	LL a,b;

	while(cin>>a>>b)

	{

		LL x0,y0;

		LL x,y;

		LL gcd=extgcd(a,x0,b,y0);

		if(1%gcd!=0)

		{

			puts("sorry");

			continue;

		}

		x=x0*1/gcd;

		y=y0*1/gcd;

		if(x<0)

		{

			x=x+b/gcd;//就是这里喔，虽然gcd肯定为1，但是为了让自己能尽快的熟练扩展欧几里德，还是坚持写全了

			y=y-a/gcd;//其实原式子是 x=x+b/gcd*t（t为一个整数，因为运用了循环所以t不用管了）

		}

		cout<<x<<" "<<y<<endl;

	}

}