拓展欧几里得算法：

1. 概述：

不仅能求出两个正整数m和n的最大公因数d，还能求出两个整数x和y(不一定为正)使得mx+ny=d

2. 分析：

这个其实挺简单的步骤如下:

• 我们假设m是d的a倍；n是d的b倍，而a和b我们是可以通过求最大公因数d来求出来的
• 原式可以化为：ax+by=1;
• 这就是一个简单的一次方程了，我们可以得到方程的无穷多种解；
• 对于给定的x。y=（1-ax）/ b。
• 这种情况给出的是一般解，我们要给出整个方程的通解
• 这个一个非齐次方程，通解等于对应齐次方程的通解+自身的一个特解

最后得

x=x0+b*t

y=y0- a*t

3. Java实现如下：

GCF gcf = new GCF();
public String findResult(int a,int b){
    int g = gcf.FindGCF(a,b);
    int k1,k2;
    k1=a/g;
    k2=b/g;
    return "y=(1 - "+k1+"x) / "+k2;
}

• 这里只对一般解进行求值。具体求通解。并不难，自己实现~

GCF类的代码

public class GCF {

    /**
     * @Mehtods:递归方法实现找最大公因数
     * */
    public int reFindGCD(int a,int b){
        if(b==0){
            return a;
        }else{
            return reFindGCD(b,a%b);
        }
    }

    /**
     * @Methods:非递归找最大公因数，辗转相除法
     * */
    public int FindGCF(int a,int b){
        int min=Math.min(a,b);
        int max=Math.max(a,b);
        while(max%min!=0){
            int temp=max%min;
            max=min;
            min=temp;
        }
        return min;
    }
    /**
     * @Methods:找最小公倍数，辗转相除法
     * */
    public int FindLCM(int a,int b){
        int gcf=FindGCF(a,b);
        int k=1;
        while((gcf*k)%a!=0||(gcf*k)%b!=0){
            k++;
        }
        return gcf*k;
    }
}