学步园

        /// <summary>
        /// 求解xm + ny = d(d为m,n的最大公约数)
        /// </summary>
        /// <param name="m"></param>
        /// <param name="n"></param>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <returns></returns>
        public static void oglidExtension(long m, long n, ref long x, ref long y)
        {
            if (m < n)
            {
                oglidExtension(n, m, ref x, ref y);
                return;
            }
            if (n == 0)
            {
                x = 1;
                y = 0;
                return;
            }

            else
            {
                long q = m % n;
                oglidExtension(n, q, ref x, ref y);
                long temp = x;
                x = y;
                y = temp - m / n * y;
            }

        }

 

算法讲解:(现在没时间了,得上班,呵呵,下来有空再详细讲解)

 

算法思想:

 

欧几里德定理大致是这样的:

存在整数 a,b和a,b的最大公约数gcd(a,b)

那么必然存在x,y使得ax+by=gcd(a,b)

 

思想:前提,欧几里德定义

假设:ax1+by1 = gcd(a,b)成立,如果b=0那么gcd(a,b) = 0;

此时令x1=1,y1=0即可得到正解

如果b!=0那么gcd(b,a% b) = gcd(b,a-a/b*b)

那么根据我们的假设有 bx2 + (a-a/b*b))y2 = gcd(b,a-a/b*b)

因而 ax1 + by1 = bx2 + (a-a/b*b))y2 = ay2 + (x2-a/by2)b

故而有 x1 = y2, y1 = x2 – a/by2

而,对于任意的a,b 如果 b!=0就进行如下迭代 a = b, b = a%b

最终必然有 b=0

那么我们可以根据上述定理来进行迭代求解

a	b	a/b	r	X=1	Y=0
15	9	1	6	1	0
9	6	1	3	0	-1
6	3	2	0	-1	2
3	0	END	END	ENE	END