IT源码网

Greatest Common Divisor讲解

wyy 2021年05月16日 编程语言 138 0

最大公约数(GCD, Greatest Common Divisor)

常用的方法为辗转相除法,也称为欧几里得算法。不妨设函数gcd(a, b)是自然是ab的最大公约数,不妨设a > b, 则有 a=b×p+qa =b×p+q, 那么对于gcd(b, q)则是bq的最大公约数,也就是说gcd(b, q)既能整除b, 又能整除a(因为 a=b×p+qa =b×p+q, p是整数),如此反复最后得到gcd(a, b) = gcd(c, 0), 第二个数为0时直接返回c. 如果最开始a < b, 那么gcd(b, a % b) = gcd(b, a) = gcd(a, b % a).

关于时间复杂度的证明:可以分a > b/2a < b/2证明,对数级别的时间复杂度,过程略。

与最大公约数相关的还有最小公倍数(LCM, Lowest Common Multiple), 它们两者之间的关系为 lcm(a,b)×gcd(a,b)= |ab|lcm(a,b)×gcd(a,b)=∣ab∣.

public static long gcd(long a, long b) { 
    return (b == 0) ? a : gcd(b, a % b); 
}

Problem

给定平面上两个坐标 P1=(x1, y1), P2=(x2,y2), 问线段 P1P2 上除 P1, P2以外还有几个整数坐标点?

Solution

问的是线段 P1P2, 故除 P1,P2以外的坐标需在 x1,x2,y1,y2范围之内,且不包含端点。在两端点不重合的前提下有:

y−y1x−x1=x2−x1y2−y1那么若得知 M=gcd(x2−x1,y2−y1)M = gcd(x_2 - x_1, y_2 - y_1)M=gcd(x2−x1,y2−y1), 则有 x−x1x - x_1x−x1 必为 x2−x1/Mx_2 - x_1 / Mx2−x1/M 的整数倍大小,又因为 x1<x<x2 x_1 < x < x_2x1<x<x2, 故最多有 M−1M - 1M−1个整数坐标点。

扩展欧几里得算法

求解整系数 x 和 y 满足 d=gcd(a,b)=ax+byd = gcd(a, b) = ax + byd=gcd(a,b)=ax+by, 仿照欧几里得算法,应该要寻找 gcd(b,a%b)=bx′+(a%b)y′gcd(b, a % b) = bx′+(a%b)y′.

public class Solution { 
    public static int gcd(int a, int b) { 
        return b == 0 ? a : gcd(b, a % b); 
    } 
 
    public static int[] gcdExt(int a, int b) { 
        if (b == 0) { 
            return new int[] {a, 1, 0}; 
        } else { 
            int[] vals = gcdExt(b, a % b); 
            int d = vals[0]; 
            int x = vals[2]; 
            int y = vals[1]; 
            y -= (a / b) * x;//减去偏移量 
            return new int[] {d, x, y}; 
        } 
    } 
 
    public static void main(String[] args) { 
        int a = 4, b = 11; 
        int[] result = gcdExt(a, b); 
        System.out.printf("d = %d, x = %d, y = %d.\n", result[0], result[1], result[2]); 
    } 
}

发布评论

分享到:

IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

分治法 - Divide and Conquer讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。