本文主要是介绍CF 7C Line(拓展欧几里得求线性方程),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
链接:
http://codeforces.com/problemset/problem/7/C
题目大意:
给方程Ax + By + C = 0. 其中A,B,C为已知, 求x,y。
分析与总结:
拓展欧几里得算法的模板题。这个算法在数论书或者网上都可以找到。
该算法求出线性方程Ax + By = gcd(A, B);
然后,这个方程可进行转换:
Ax + By = gcd(A, B)
=> Ax + By = -C/z, 其中-C/z = gcd(A, B)
=> Ax*z + By*z = C.
其中x, y可以通过拓展欧几里得算法求出,
然后,我们只需要求出z, 而z = -C/gcd(A,B);
所以, 最终答案x = x*(-C/gcd(A,B)) , y = y*(-C/gcd(A,B));
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL INF = 5*1e18;void gcd(LL a, LL b, LL& d,LL& x, LL& y){if(!b){d=a; x=1; y=0; }else {gcd(b,a%b,d,y,x); y -= x*(a/b); }
}int main(){LL a,b,c,d,x,y;cin >> a >> b >> c;gcd(a,b,d,x,y);if(c%d != 0)puts("-1");else cout << -x*(c/d) << " " << -y*(c/d) << endl;return 0;
}
—— 生命的意义,在于赋予它意义士。
原创 http://blog.csdn.net/shuangde800 , By D_Double (转载请标明)
这篇关于CF 7C Line(拓展欧几里得求线性方程)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!