CF 7C Line(拓展欧几里得求线性方程)

题目大意：
给方程Ax + By + C = 0.  其中A，B，C为已知， 求x，y。

分析与总结：
拓展欧几里得算法的模板题。这个算法在数论书或者网上都可以找到。
该算法求出线性方程Ax + By = 易做图(A, B); 
然后，这个方程可进行转换:
       Ax + By = 易做图(A, B)
=>  Ax + By = -C/z， 其中-C/z = 易做图(A, B)
=>  Ax*z + By*z = C. www.zzzyk.com
其中x, y可以通过拓展欧几里得算法求出，
然后，我们只需要求出z， 而z = -C/易做图(A,B);
所以， 最终答案x = x*(-C/易做图(A,B)) ,  y = y*(-C/易做图(A,B)); 

代码：
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
using namespace std; 
typedef long long LL; 
const LL INF = 5*1e18; 
 
void 易做图(LL a, LL b, LL& d,LL& x, LL& y){ 
    if(!b){d=a; x=1; y=0; } 
    else {易做图(b,a%b,d,y,x); y -= x*(a/b); } 
} 
 
int main(){ 
    LL a,b,c,d,x,y; 
    cin >> a >> b >> c; 
    易做图(a,b,d,x,y); 
    if(c%d != 0) 
        puts("-1"); 
    else  
        cout << -x*(c/d) << " " << -y*(c/d) << endl; 
    return 0; 
} 

补充：软件开发 , C++ ,

上一个：华中科大校赛预赛1606 Naive
下一个：A + B 九度oj