辗转相除以及辗转相减法

文章目录

• 前言
• 辗转相除法（又名欧几里算法）
• 辗转相减法（又名更相减损法）
• 原始辗转相减法
• 改版辗转相减法（减的是指数）
• 参考文章

前言

在学习Acwing c++蓝桥杯辅导课第八讲数论-AcWing 1223. 最大比例时有使用到求指数的最大公约数，这里来记录下知识点。

当前文章已收录到博客文件目录索引：博客目录索引(持续更新)

辗转相除法（又名欧几里算法）

应用：辗转相除实际也就是欧几里得算法，主要是求两个整数的最大公约数。

举例：gcd(5^2^，5^3^) = 5^2^

注意：而针对于指数形式的要求得的最大公约数则需要使用辗转相减法。

代码：时间复杂度O(logn)。

class Solution {

    //欧几里得算法(辗转相除法)
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static void main(String[] args) {
        System.out.println(gcd(12, 5));
    }
}

辗转相减法（又名更相减损法）

原始辗转相减法

场景：更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

原理：gcd(a,b)=gcd(b,a−b)。

代码实现：

public static int gcd_sub(int a, int b) {
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    return a;
}

改版辗转相减法（减的是指数）

算法题：AcWing 1223. 最大比例

通过辗转相减法gcd(x,y) = gcd(y,x%y) = gcd(y,x−y)来进行推导：f(p^x^,p^y^) = p^gcd(x,y)^ = p^gcd(y,x−y)^ = f(p^y^,p(^x−y^)) = f(p^y^,$\frac{px}{py}$)，即可以求

求p^x^和p^y^幂的最大公约数次幂p^gcd(x,y)^。

应用：辗转相减法可以用来求若干个形如( $\frac{p}{q}$)^ri^的数的最大公约数。

举例（指数的最大公约数）：gcd_sub(5^2^，5^3^) = 5^1^

算法推导过程：f(p^x^,p^y^) = p^(x,y)^ = p^(y,x−y)^ = f(p^y^,p(^x−y^)) = f(p^y^,$\frac{px}{py}$)

• $\frac{p}{q}$不可以再表示为次幂的形式。
• p、q、ri均为正整数。

代码：时间复杂度O(n)

class Solution {

    /**
     * 辗转相减法（指数的最大公约数）
     * @return
     */
    public static int gcd_sub(int a, int b) {
        if (b == 1) return a;
        if (a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        return gcd_sub(b, a / b);
    }

    public static void main(String[] args) {
        System.out.println(gcd_sub(25, 125));
    }
}

---

参考文章

[1]. 辗转相减法

[2]. 【最大公约数 GCD】 --- 常用四大算法（辗转相除法，穷举法，更相减损法，Stein算法）

[3]. 数论-辗转相减法-第七届蓝桥杯省赛C++A/B组-最大比例