扩展欧几里得

扩展欧几里得定理
扩展欧几里得定理（Extended Euclidean algorithm, EXGCD），常用于求ax+by=gcd(a,b) 的一组可行解。

将 不断代入递归求解直至 （最大公约数，下同）为 0 递归 x=1,y=0 回去求解。

public static int f(int a,int b,int[] xy){
        if(b == 0){
            xy[0] = 1;
            xy[1] = 0;
            return a;
        }
        int gcd = f(b,a%b,xy);
        int t = xy[0];  //t = x2;
        xy[0] = xy[1];  //x1 = y2;
        xy[1] = t - a/b*xy[1];  //y1 = x2 - a/b*y2
        return gcd;
    }

这里要传一个数组，因为，最后要获取被改变的x，y的值。c语言用指针也可以，传地址。

函数参数的传递的是值，swap(int a,int b)中，a和b都只是得到了实参的值而已，然后就跟实参没有任何关系了。

如果用swap(int* a,int* b)，依然是得到实参的值，但由于a,b是指针，得到的将是地址，那么参数和实参所指的地址是一样的，如果在函数体里交换地址所指的存储内的东西，那么就是真的交换了。