首页 > 代码库 > 裴蜀定理
裴蜀定理
最大公约数:d = gcd(a,b)
裴蜀定理:存在u,v使得a*u + b*v = d
裴蜀定理特例:若a,b互质,gcd(a,b) = 1则存在u,v 使得a*u + b*v = 1
裴蜀定理 pdu + qdv = d ->pu + qv = 1
证明:
直接构造出u,v
au + bv = d
(a-b)u + b(u+v) = d
令a’ = a%b, 令t使得a = b*t + a’
t = (a-a’)/b
(a-tb)u + b(tu + v) = d
a’u + b(tu+v) = d
令v’ = tu+v, 得到a’u + bv’ = d
v = v’ – tu 若知道(u, v’)则可知道(u,v)
代码实现:
int gcd(int a, int b){ return b==0?a:gcd(b,a%b); } int ex_gcd(int a,int b, int &u, int &v){ If (b == 0){ u = 1, v = 0; Return a; } int d = ex_gcd(b, a%b, v, u);//反转 v = v - a/b *u; //容易溢出 return d; }看完了,觉得用处不是很大,找了一道题看了下,作为应用参考吧。
链接:http://blog.csdn.net/acdreamers/article/details/12347475
裴蜀定理
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。