题解
注意$a$,$b$可以交换位置。
之后就是简单的解方程了。
要使$|x|+|y|$最小，需要保证$x$最小，之后保证$y$最小即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
typedef long long ll;
ll a,b,d,x1,x2,y1,y2;
ll gcd(ll aa,ll bb){
return bb?gcd(bb,aa%bb):aa;
}
ll extgcd(ll aa,ll bb,ll &xx,ll &yy){
if(!bb){
xx=1,yy=0;
return aa;
}
ll dd=extgcd(bb,aa%bb,yy,xx);
yy-=(aa/bb)*xx;
return dd;
}
ll Abs(ll x){
return (x<0)?(-x):x;
}
void work(ll a_,ll b_,ll &x,ll &y){
ll g=extgcd(a_,b_,x,y),t=b_/g;
x*=d/g,x=(x%t+t)%t;
y=Abs((a_*x-d)/b_);
}
int main(){
for(;;){
scanf("%lld%lld%lld",&a,&b,&d);
if(!a&&!b&&!d)break;
work(a,b,x1,y1);
work(b,a,x2,y2);
if(x1+y1<x2+y2)printf("%lld %lld\n",x1,y1);
else printf("%lld %lld\n",y2,x2);
}
return 0;
}