CodeForces 7C （扩展欧几里得）

题目链接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=96545#problem/B

Description

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·10¹⁸ to 5·10¹⁸ inclusive, or to find out that such points do not exist.

Input

The first line contains three integers A, B and C ( - 2·10⁹ ≤ A, B, C ≤ 2·10⁹) — corresponding coefficients of the line equation. It is guaranteed that A² + B² > 0.

Output

If the required point exists, output its coordinates, otherwise output -1.

Sample Input

Input

2 5 3

Output

6 -3

这道题是扩展欧几里得模板（用于线性方程和方程组中）：  欧几里得定理：ax+by==gcd(a，b)

void Solve(long long a, long long b, long long &x, long long &y)
{
    long long t;

    if (b == 0)
    {
        x = 1;
        y = 0;

        return ;
    }

    Solve(b, a%b, x, y);

    t = x;
    x = y;
    y = t - (a/b)*y;
}

注意：这里的a和b是除以公约数之后的值

证明：1.当b=0时gcd（a， b）= a，由定理得a*x + b*y = a，即a*x = a，那么可以得到其中一组解是：x = 1；y = 0；

2.x,y表示第一次递归时的值，x1,y1表示第二次递归时的值。那么gcd(a,b)==gcd(b,a%b)，同时都代入式ax+by==gcd(a，b)，有ax+by==b*x1+(a%b)*y1。将右边变形一下，b*x1+(a%b)*y1==b*x1+(a-(a/b)*b)*y1==a*y1+b*(x1-(a/b)*y1)，最终得到ax+by==a*y1+b*(x1-(a/b)*y1)，所以x=y1，y=（x1-（a/b）*y1）。
最终递归得到的x和y就是这个线性方程的一组解。

下面是这道题的代码：

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int N=1e6+10;

long long Gcd(long long a, long long b)
{
    return b == 0 ? a : Gcd(b, a % b);
}

void Solve(long long a, long long b, long long &x, long long &y)
{
    long long t;

    if (b == 0)
    {
        x = 1;
        y = 0;

        return ;
    }

    Solve(b, a%b, x, y);

    t = x;
    x = y;
    y = t - (a/b)*y;
}

int main ()
{
    long long a, b, c, d, x, y;

    while (scanf("%lld %lld %lld", &a, &b, &c) != EOF)
    {
        d = Gcd(a, b);

        if (c % d != 0) printf("-1
");
        else
        {
            a = a / d;
            b = b / d;
            c = c / d;

            Solve(a, b, x, y);

            x *= -c;
            y *= -c;

            printf("%lld %lld
", x, y);
        }
    }

    return 0;
}