MyException - 我的异常网
当前位置:我的异常网» C++ » 欧几里德算法gcd及其拓展最终解释

欧几里德算法gcd及其拓展最终解释

www.MyException.Cn  网友分享于:2015-08-24  浏览:0次
欧几里德算法gcd及其拓展终极解释

这个困扰了自己好久,终于找到了解释,还有自己改动了一点点,耐心看完一定能加深理解

 
扩展欧几里德算法-求解不定方程,线性同余方程。
  设过s步后两青蛙相遇,则必满足以下等式:
    (x+m*s)-(y+n*s)=k*l(k=0,1,2....)
  稍微变一下形得:
    (n-m)*s+k*l=x-y
令n-m=a,k=b,x-y=c,即
    a*s+b*l=c
  只要上式存在整数解,则两青蛙能相遇,否则不能。
  首先想到的一个方法是用两次for循环来枚举s,l的值,看是否存在s,l的整数解,若存在则输入最小的s,
但显然这种方法是不可取的,谁也不知道最小的s是多大,如果最小的s很大的话,超时是明显的。
  其实这题用欧几里德扩展原理可以很快的解决,先来看下什么是欧几里德扩展原理:
  欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:
  定理:gcd(a,b) = gcd(b,a mod b)
  证明:a可以表示成a = kb + r,则r = a mod b
  假设d是a,b的一个公约数,则有
  d|a, d|b,而r = a - kb,因此d|r
  因此d是(b,a mod b)的公约数
  假设d 是(b,a mod b)的公约数,则
 d | b , d |r ,但是a = kb +r
  因此d也是(a,b)的公约数
  因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证
  欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为: 
  int Gcd(int a, int b)   {   if(b == 0)   return a; return Gcd(b, a % b);   }
  当然你也可以写成迭代形式:
  int Gcd(int a, int b)   {   while(b != 0)   {   int r = b;    b = a % b;    a = r;   }   return a;   }
  本质上都是用的上面那个原理。
  补充: 扩展欧几里德算法是用来在已知a, b求解一组x,y使得a*x+b*y=Gcd(a,b)(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使
用C++的实现:
  int exGcd(int a, int b, int &x, int &y)   {   if(b == 0)   {   x = 1;   y = 0;    return a;   }   int r = exGcd(b, a % b, x, y);   int t = x;   x = y;   y = t - a / b * y;    return r;   }  
把这个实现和Gcd的递归实现相比,发现多了下面的x,y赋值过程,这就是扩展欧几里德算法的精髓。
  可以这样思考:
  对于a' = b, b' = a % b 而言,我们求得 x, y使得 a'x + b'y = Gcd(a', b')
  由于b' = a % b = a - a / b * b (注:这里的/是程序设计语言中的除法)
  那么可以得到:
  a'x + b'y = Gcd(a', b') ===>   bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b) ===>   ay +b(x - a / b*y) = Gcd(a, b)
  因此对于a和b而言,他们的相对应的p,q分别是 y和(x-a/b*y).
求解 x,y的方法的理解
  设 a>b。
  1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
  2,ab<>0 时
  设 ax1+by1=gcd(a,b);
  bx2+(a mod b)y2=gcd(b,a mod b);
  根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
  则:ax1+by1=bx2+(a mod b)y2;
  即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
  根据恒等定理得:x1=y2; y1=x2-(a/b)*y2;
  这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于 x2,y2.
  上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候 b=0,所以递归可以
 结束。
  在网上看了很多关于不定方程方程求解的问题,可都没有说全,都只说了一部分,看了好多之后才真正弄清楚不定方程的求解全过程,步骤如下:
  求a * x + b * y = c的整数解。
  1、先计算Gcd(a,b),若n不能被Gcd(a,b)整除,则方程无整数解;否则,在方程两边同时除以Gcd(a,b),得到新的不定方程a' * x + b' * y = c',此时Gcd(a',b')=1;
2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0,则c' * x0,c' * y0是方程a' * x + b' * y = c'的一组整数解;
  3、根据数论中的相关定理,可得方程a' * x + b' * y = c'的所有整数解为:

    其实我们求得的解只是一组,

    a*x0+lcm(a,b)+b*y0-lcm(a,b)=1;

    a*x                +b*y              =1;

    x=x0+b/gcd(a,b);y=y0-a/gcd(a,b);

    a/gcd(a,b)*x'+b/gcd(a,b)*y'=c/gcd(a,b);

    x'=c/gcd(a,b)*x0+b/gcd(a,b);y'=c/gcd(a,b)*y0-a/gcd(a,b);

 

x = c' * x0 + b' * t y = c' * y0 - a' * t (t为整数)
    上面的解也就是a * x + b * y = n 的全部整数解

文章评论

5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
中美印日四国程序员比较
中美印日四国程序员比较
为什么程序员都是夜猫子
为什么程序员都是夜猫子
每天工作4小时的程序员
每天工作4小时的程序员
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
我的丈夫是个程序员
我的丈夫是个程序员
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
代码女神横空出世
代码女神横空出世
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
10个调试和排错的小建议
10个调试和排错的小建议
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java程序员必看电影
Java程序员必看电影
漫画:程序员的工作
漫画:程序员的工作
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
程序员的鄙视链
程序员的鄙视链
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
程序员都该阅读的书
程序员都该阅读的书
 程序员的样子
程序员的样子
总结2014中国互联网十大段子
总结2014中国互联网十大段子
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
程序员必看的十大电影
程序员必看的十大电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员和编码员之间的区别
程序员和编码员之间的区别
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
编程语言是女人
编程语言是女人
一个程序员的时间管理
一个程序员的时间管理
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
旅行,写作,编程
旅行,写作,编程
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有