Codeforces Beta Round #7 C. Line (扩展欧几里德)

题目链接：http://codeforces.com/problemset/problem/7/C

给你一个直线方程，有整数解输出答案，否则输出-1。

扩欧模版题。这里有讲解：http://www.cnblogs.com/Recoder/p/5459812.html

(很久没写exgcd，都不会写了)

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

LL exgcd(LL a , LL b , LL &x , LL &y) {
    LL res = a;
    if(!b) {
        x = 1 , y = 0;
    }
    else {
        res = exgcd(b , a % b , x , y);
        LL temp = x;
        x = y;
        y = temp - a / b * y;
    }
    return res;
}

int main()
{
    LL a , b , c , gcd , x , y;
    cin >> a >> b >> c;
    gcd = exgcd(a , b , x , y);
    if(c % gcd == 0) {
        LL temp = -c / gcd;
        cout << x * temp << " " << y * temp << endl;
    }
    else {
        cout << -1 << endl;
    }
}