題目鏈接：http://codeforces.com/problemset/problem/7/C

給你一個直線方程，有整數解輸出答案，否則輸出-1。

擴歐模版題。這里有講解：http://www.cnblogs.com/Recoder/p/5459812.html

(很久沒寫exgcd，都不會寫了)

1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 5 LL exgcd(LL a , LL b , LL &x , LL &y) { 6 LL res = a; 7 if(!b) { 8 x = 1 , y = 0; 9 } 10 else { 11 res = exgcd(b , a % b , x , y); 12 LL temp = x; 13 x = y; 14 y = temp - a / b * y; 15 } 16 return res; 17 } 18 19 int main() 20 { 21 LL a , b , c , gcd , x , y; 22 cin >> a >> b >> c; 23 gcd = exgcd(a , b , x , y); 24 if(c % gcd == 0) { 25 LL temp = -c / gcd; 26 cout << x * temp << " " << y * temp << endl; 27 } 28 else { 29 cout << -1 << endl; 30 } 31 }

?

轉載于:https://www.cnblogs.com/Recoder/p/5459841.html

總結

以上是生活随笔為你收集整理的Codeforces Beta Round #7 C. Line (扩展欧几里德)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。