Go语言视频零基础入门到精通

javalearner

什么是GCD？
GCD是最大公约数的简称。在开头，我们先下几个定义：
①a|b表示a能整除b（a是b的约数）
②a mod b表示a-[a/b]b（[a/b]在java中相当于a/b）

③(a,b)表示a和b的最大公约数

④a和b的线性组合表示ax+by（x,y为整数）。我们有：若d|a且d|b，则d|ax+by（这很重要！）  线性组合与GCD
现在我们证明一个重要的定理：gcd(a,b)是a和b的最小的正线性组合。

证明：
设gcd(a,b)为d，a和b的最小的正线性组合为s
∵d|a且d|b，
∴d|s。
而a mod s=a-[a/s]s =a-[a/s](ax+by) =a(1-[a/s]x)-b[a/s]y
亦为a和b的线性组合
  
   
   
     
   

     
   
  
∵a mod s<s，a mod s不能是a和b的最小的正线性组合(因为已经假设s 是 a和b的最小的正线性组合)
∴a mod s=0，即s|a
同理由s|b
∴s为a,b的公约数
∴s<=d
∵d|s
∴d=s。证毕。 由这条定理易推知：若d|a且d|b，则d|gcd(a,b) Euclid（欧几里德）算法
现在的问题是如何快速的求gcd(a,b)。穷举明显不是一个好方法（O(n)），所以需要一个更好的方法。
首先我们先提出一个定理：gcd(a,b)=gcd(b,a-bx)（x为正整数）。 证明：
设gcd(a,b)=d,gcd(b,a-bx)=e,则
∵d|a,d|b
∴d|a-bx
∴d|gcd(b,a-bx)，即d|e

∵e|b,e|a-bx
∴e|bx+(a-bx)，即e|a
∴e|gcd(a,b)，即e|d
∴d=e。证毕。 这个定理非常有用，因为它能快速地降低数据规模。
当x=1时，gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。
当x达到最大时，即x=[a/b]时，gcd(a,b)=gcd(b,a mod b)。这个就是Euclid算法。它是不是Euclid提出的我不知道，但听说是在Euclid时代形成的，所以就叫Euclid算法了。程序非常的简单：

1. public int Gcd(int a, int b){
   
2.     　　if(b == 0)
   
3.         　　return a;
   
4.         return Gcd(b, a % b);
   
5. 　　}
   
6. 　　当然你也可以写成迭代形式：
   
7. 　public 　int Gcd(int a, int b){
   
8.     　　while(b != 0)
   
9.     　　{
   
10.         　　int r = b;
    
11. 　　        b = a % b;
    
12.     　　    a = r;
    
13.     　　}
    
14.     　　return a;
    
15. 　　}
    

复制代码

Euclid算法比辗转相减法好，不仅好在速度快，而且用起来也方便。两种算法都有一个隐含的限制：a>=b。用辗转相减法时，必须先判断大小，而Euclid算法不然。若a<b，则一次递归就会转为gcd(b,a)，接着就能正常运行了。 扩展Euclid
前面我们说过，gcd(a,b)可以表示为a和b的最小的正线性组合。现在我们就要求这个最小的正线性组合ax+by中的x和y。这个可以利用我们的Euclid算法。
从最简单的情况开始。当b=0时，我们取x=1,y=0。当b≠0时呢？
假设gcd(a,b)=d，则gcd(b,a mod b)=d。若我们已经求出了gcd(b,a mod b)的线性组合表示bx"+(a mod b)y"，则
gcd(a,b)=d
=bx"+(a mod b)y"
=bx"+(a-[a/b]b)y"
=ay"+b(x"-[a/b]y")
那么取x=y"，y=x"-[a/b]y"就可以将gcd(a,b)表示为a和b的最小的正线性组合，这样就可以在Euclid的递归过程中求出x和y。

程序：

1. import java.util.Scanner;
   
2. public class GED {
   
3.     static long x0, y0;
   
4.     public static void main(String[] args) {
   
5.         Scanner scan = new Scanner(System.in);
   
6.         long a = scan.nextInt();
   
7.         long b= scan.nextInt();
   
8.         
   
9.         
   
10.         long d = gcd(a , b);
    
11.         //这个地方太麻烦了，将就吧
    
12.         System.out.println("gcd("+a+","+b+")="+a+"*"+x0+"+"+b+"*"+y0);
    
13.     }
    
14. //将gcd(a,b)表示为a,b的线性组合。
    
15.     public static long gcd(long a, long b) {
    
16.         long t, d;
    
17.         if (b == 0) {
    
18.             x0 = 1;
    
19.             y0 = 0;
    
20.             return a;
    
21.         }
    
22.         d = gcd(b, a % b);
    
23.         t = x0;
    
24.         x0 = y0;
    
25.         y0 = t - a / b * y0;
    
26.        // System.out.println("a="+a+"  b="+b+"  x0="+x0+"   y0="+y0);
    
27.         return d;
    
28.     }
    
29. }
    

复制代码

我们现在还有一个问题：x,y是不是确定的？答案：不是。如果x,y符合要求，那么x+bk,y-ak也符合要求。不确定的原因在于这一句：“当b=0时，我们取x=1,y=0。”实际上y可以取任何正整数。 不定方程ax+by=c
    现在终于到了本文重点：解二元一次不定方程。看起来扩展Euclid算法是不定方程的一种特殊情况，实际上呢，不定方程却是用Euclid算法解的。
对于不定方程ax+by=c，设gcd(a,b)=d，如果ax+by=c有解，则d|c（这也是许多奥数题的切入点）。所以一旦d不是c的约数，那么ax+by=c一定无解。当d|c时，先求出ax"+by"=d=gcd(a,b)的x"和y"，则x=x"*c/d，y=y"*c/d。由上一段可知，只要ax+by=c有一个解，它就有无数个解。

程序：

1. import java.util.Scanner;
   
2. public class Main {
   
3.     static long x0, y0;
   
4.     public static void main(String[] args) {
   
5.         Scanner scan = new Scanner(System.in);
   
6.         long a = scan.nextInt();
   
7.         long b= scan.nextInt();
   
8.         long c= scan.nextInt();
   
9.         
   
10.         long d = gcd(a , b);
    
11.         if(c%d!=0){
    
12.             System.out.println("Impossible");
    
13.         }else{
    
14.             long x1 = x0*c/d ;
    
15.             long y1=y0*c/d;
    
16.             System.out.println("x1="+x1+"  y1="+y1);
    
17.         }
    
18.     }
    
19.     public static long gcd(long a, long b) {
    
20.         long t, d;
    
21.         if (b == 0) {
    
22.             x0 = 1;
    
23.             y0 = 0;
    
24.             return a;
    
25.         }
    
26.         d = gcd(b, a % b);
    
27.         t = x0;
    
28.         x0 = y0;
    
29.         y0 = t - a / b * y0;
    
30.        // System.out.println("a="+a+"  b="+b+"  x0="+x0+"   y0="+y0);
    
31.         return d;
    
32.     }
    
33. }
    

复制代码

C:ww>java Main
12
8
36
x1=9 y1=-9


  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/3/000711718.zip