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 =  , y = ;

     }

     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 == ) {

         LL temp = -c / gcd;

         cout << x * temp << " " << y * temp << endl;

     }

     else {

         cout << - << endl;

     }

 }