链接:
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 (转载请标明)
分享到:
相关推荐
拓展欧几里得-求解二元一次方程.cpp
扩展欧几里得算法求逆元
用PHP实现欧几里得和拓展欧几里得计算的程序。
此文档是拓展欧几里得的ppt,里面还囊括了费马小定理,逆元,欧拉降幂相关的,可谓应有尽有
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
模式识别中对数据进行欧式分类 线性分类 使用matlab程序
用扩展欧几里得算法求任意两个数字的最大公因数
密码学考试复习(关于快速指数算法和扩展欧几里得求逆元),之前考试自己整理的,今天又要学了。里面的算法还能看,还整理的比较透彻当时。备用了留在这。不知道为什么之前上传的xmind一点就跳转到别的页面了,这次...
当a,b,且a互质时,计算ax+by=1的值, 是计算RSA密钥的基本步骤之一。
java语言实现的欧几里得算法,求最大公约数,以及满足(a,b)=x*a+y*b的x和y
欧几里得减法求最大公约数,欧几里得减法求最大公约数
matlab的M函数文件,附带了函数的使用说明了
RSA编码实现,创建公钥和私钥,并判定生成的是否是素数,生成界面和菜单便于用户选择,用扩展欧几里得短发求乘法逆元,快速模幂算法,
Python 机器学习 欧几里得距离
正在使用广义欧几里得除法运行计算(520,3344),运算过程如下: 3344 = 6 · 520 + 224 520 = 2 · 224 + 72 224 = 3 · 72 + 8 72 = 9 · 8 + 0 ...拓展欧几里得除法得 s = -45.0,t = 7.0。
ACM数论基础知识入门之扩展欧几里得算法
用欧几里得算法求最大公约数的c++代码,很完整,可以运行
欧几里得算法的应用 欧几里得算法的应用 欧几里得算法的应用