time limit per test : 1 second
memory limit per test : 256 megabytes

A line on the plane is described by an equation $Ax+By+C=0$. You are to find any point on this line, whose coordinates are integer numbers from  $-5\cdot 10^{18}$ to $5\cdot 10^{18}$ inclusive, or to find out that such points do not exist.
Input

The first line contains three integers A, B and C $(-2\cdot 10^9\le A,B,C\le 2\cdot 10^9)$ — corresponding coefficients of the line equation. It is guaranteed that $A^2+B^2>0$.
###Output
If the required point exists, output its coordinates, otherwise output $-1$.
####Examples
Input

2 5 3
1

Output

6 -3
1

题意：
模板题，求方程 $Ax+By+C=0$ 的一个整数解。
题解：
扩展欧几里得

#include<bits/stdc++.h>
#define base 107
#define ll long long
using namespace std;
ll  exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;return a;
    }
    ll d=exgcd(b,a%b,x,y),temp=x;
    x=y;
    y=temp-a/b*y;
    return d;
}
ll a,b,ta,tb,c,d,x,y;
int main(){
    scanf("%I64d%I64d%I64d",&a,&b,&c);
    ta=abs(a);tb=abs(b);
    d=exgcd(ta,tb,x,y);
    if(-c%d!=0)return puts("-1"),0;
    c/=d;
    x*=-c;y*=-c;
    if(a<0)x=-x;
    if(b<0)y=-y;
    printf("%I64d %I64d\n",x,y);
    return 0;
}

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