文章目录

• • • 1. 最大公约数
    • 2. 最小公倍数
    • 3. 模取幂

1. 最大公约数

欧几里得算法(辗转相除法)求最大公约数(Greatest Common Divisor，GCD)的递归定理：对任意非负整数a和任意正整数b
g c d ( a , b ) = g c d ( b , a   m o d   b ) gcd(a,b)=gcd(b,a \ mod \ b) gcd(a,b)=gcd(b,a mod b)
欧几里得算法递归实现：

// 欧几里得算法递归实现
public static int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

欧几里得算法非递归实现：

// 欧几里得算法非递归实现
public static int gcd(int a, int b) {
    int r;
    while (b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

2. 最小公倍数

根据最大公约数的定义有： a = k 1 ⋅ g c d ( a , b ) ， b = k 2 ⋅ g c d ( a , b ) a=k_1 \cdot gcd(a,b)，b=k_2 \cdot gcd(a,b) a=k1​⋅gcd(a,b)，b=k2​⋅gcd(a,b)；公倍数满足被a和b整除，那么公倍数必须是 k 1 k_1 k1​和 k 2 k_2 k2​乘积的倍数，要求最小则再乘以 g c d ( a , b ) gcd(a,b) gcd(a,b)，即：
l c m ( a , b ) = k 1 × k 2 × g c d ( a , b ) = a g c d ( a , b ) × b g c d ( a , b ) × g c d ( a , b ) = a × b g c d ( a , b ) a × b = g c d ( a , b ) × l c m ( a , b ) lcm(a,b)=k_1 \times k_2 \times gcd(a,b)=\frac{a}{gcd(a,b)} \times \frac{b}{gcd(a,b)} \times gcd(a,b)=\frac{a\times b}{gcd(a,b)}\\ a\times b = gcd(a,b) \times lcm(a,b) lcm(a,b)=k1​×k2​×gcd(a,b)=gcd(a,b)a​×gcd(a,b)b​×gcd(a,b)=gcd(a,b)a×b​a×b=gcd(a,b)×lcm(a,b)
求最小公倍数代码实现：

// 求最小公倍数
public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

3. 模取幂

模取幂：求一个数的幂对另一个数的模运算， a b   m o d   n a^b \ mod \ n ab mod n

// 模取幂：Math.pow(a, b) % n
// a, b为非负整数，n为正整数
public static int modularExponentiation(int a, int b, int n) {
    int c = 0;
    int d = 1;
    String binaryB = Integer.toBinaryString(b);
    for (int i = 0; i < binaryB.length(); i++) {
        c *= 2;
        d = (d * d) % n;
        if (binaryB.charAt(i) == '1') {
            c++;
            d = (d * a) % n;
        }
    }
    return d;
}