exgcd
应分为2种情况分类讨论
显然我们可以列出方程
ax-by=±d
当方程右侧为-d时，可得
by-ax=d
于是我们就得到了2个方程：
ax-by=d
by-ax=d -> bx-ay=d
分别跑一遍exgcd，取abs(a)+abs(b)更小的那个
注意第二种情况先输出y,因为y对应a
#include<cstdio>
#include<cmath>
int a,b,d,xx,yy,x2,y2,g,p; //y1不能用..
void exgcd(int a,int b,int &x,int &y){
if(!b) x=,y=,g=a;
else exgcd(b,a%b,y,x),y-=x*(a/b);
}
void work(int a,int b,int &x,int &y){
exgcd(a,b,x,y);
x*=d/g; p=b/g; //exgcd求的方程右侧为gcd(a,b),所以要 *d/gcd(a,b)
x=(x%p+p)%p; 根据性质得最小解
y=abs((a*x-d)/b);
}
int main(){
while(scanf("%d%d%d",&a,&b,&d)&&a+b+d){
work(a,b,xx,yy);
work(b,a,x2,y2);
if(xx+yy<x2+y2) printf("%d %d\n",xx,yy);
else printf("%d %d\n",y2,x2); //倒着输出
}return ;
}