CFR 7 C. Line ( Extgcd, Math )

http://codeforces.com/contest/7/problem/C

題意：
給一個方程式 Ax + By + C = 0，找一組整數 ( x, y ) 在該直線上。或者判斷不存在。

解法：
先用 ext_gcd 判斷 Ax + By = gcd( A, B ) 時的 x, y 分別是多少。
ext_gcd 要背！不懂還是要硬背！( 我總是想不起來第 15 行 )

int A, B, C;

void init(){
  cin >> A >> B >> C;
}

void ext_gcd( int a, int b, int &d, int &x, int &y ){
  if( not b ){
    d = a;
    x = 1;
    y = 0;
    return;
  }
  ext_gcd( b, a % b, d, y, x );
  y -= x * ( a / b );
}

void preprocess(){

}

void solve(){
  int d, x, y;
  ext_gcd( A, B, d, x, y );
  if( -C % d != 0 ){
    cout << -1 << endl;
    exit( 0 );
  }
  cout << x * -C / d << " " << y * -C / d << endl;
}