每日算法 — 使用java实现快速幂取模：二进制拆分与模运算优化

问题描述

快速幂取模是计算 a^b mod m 的高效算法。直接计算 a^b 再取模会导致中间结果极其庞大（当 b 很大时），甚至超出任何基本数据类型的表示范围。快速幂算法通过二进制拆分思想，将时间复杂度从 O(b) 优化到 O(log b)，是数论、密码学和竞赛编程中的核心技巧。

算法思路

核心思想：二进制拆分

将指数 b 表示为二进制形式。例如 b = 13 = 1101₂ = 8 + 4 + 1：

a^13 = a^(8+4+1) = a^8 × a^4 × a^1

通过不断平方，可以在 O(log b) 步内计算出 a^1, a^2, a^4, a^8, ...。

模运算性质

(a × b) mod m = ((a mod m) × (b mod m)) mod m

这意味着我们可以在每一步乘法后立即取模，避免大数溢出。

迭代实现（更优）

result = 1
while b > 0:
    if b & 1 == 1:    // 如果b的最低位是1
        result = result * a % m
    a = a * a % m     // a平方
    b >>= 1           // b右移一位

Java实现

基础快速幂

public class FastModularExponentiation {
    /**
     * 快速幂取模（迭代版）
     * 计算 (base^exponent) mod modulus
     * 时间复杂度：O(log exponent)
     * 空间复杂度：O(1)
     *
     * @param base     底数
     * @param exponent 指数（非负）
     * @param modulus  模数（正数）
     * @return (base^exponent) % modulus
     */
    public static long fastPow(long base, long exponent, long modulus) {
        if (modulus <= 0) {
            throw new IllegalArgumentException("modulus must be positive");
        }
        if (exponent < 0) {
            throw new IllegalArgumentException("exponent must be non-negative");
        }
        if (modulus == 1) {
            return 0;
        }

        long result = 1 % modulus;
        base %= modulus;

        while (exponent > 0) {
            // 如果exponent的最低位是1，将当前base乘入结果
            if ((exponent & 1) == 1) {
                result = (result * base) % modulus;
            }
            // base平方，exponent右移
            base = (base * base) % modulus;
            exponent >>= 1;
        }

        return result;
    }

    /**
     * 快速幂取模（递归版）
     */
    public static long fastPowRecursive(long base, long exponent, long modulus) {
        if (modulus <= 0) {
            throw new IllegalArgumentException("modulus must be positive");
        }
        if (exponent == 0) {
            return 1 % modulus;
        }

        base %= modulus;
        long half = fastPowRecursive(base, exponent >> 1, modulus);
        half = (half * half) % modulus;

        if ((exponent & 1) == 1) {
            half = (half * base) % modulus;
        }
        return half;
    }

    public static void main(String[] args) {
        // 基础测试
        System.out.println("2^10 mod 1000 = " + fastPow(2, 10, 1000)); // 24
        System.out.println("3^100 mod 100 = " + fastPow(3, 100, 100)); // 1

        // 大数测试：2^1000000000 mod 1000000007
        long start = System.currentTimeMillis();
        long result = fastPow(2, 1_000_000_000L, 1_000_000_007L);
        long end = System.currentTimeMillis();
        System.out.println("2^1000000000 mod 1000000007 = " + result);
        System.out.println("耗时：" + (end - start) + " ms");

        // 验证与朴素算法的一致性
        long base = 7, exp = 15, mod = 100000;
        long fast = fastPow(base, exp, mod);
        long naive = 1;
        for (int i = 0; i < exp; i++) {
            naive = (naive * base) % mod;
        }
        System.out.println("一致性验证：" + (fast == naive ? "通过" : "失败"));
    }
}

扩展：矩阵快速幂

/**
 * 矩阵类，支持矩阵乘法和快速幂
 */
class Matrix {
    long[][] data;
    int n;

    Matrix(int n) {
        this.n = n;
        this.data = new long[n][n];
    }

    Matrix(long[][] data) {
        this.n = data.length;
        this.data = new long[n][n];
        for (int i = 0; i < n; i++) {
            System.arraycopy(data[i], 0, this.data[i], 0, n);
        }
    }

    static Matrix identity(int n) {
        Matrix m = new Matrix(n);
        for (int i = 0; i < n; i++) {
            m.data[i][i] = 1;
        }
        return m;
    }

    Matrix multiply(Matrix other, long mod) {
        Matrix result = new Matrix(n);
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                if (data[i][k] == 0) continue;
                for (int j = 0; j < n; j++) {
                    result.data[i][j] = (result.data[i][j] + data[i][k] * other.data[k][j]) % mod;
                }
            }
        }
        return result;
    }

    Matrix pow(long exponent, long mod) {
        Matrix result = identity(n);
        Matrix base = new Matrix(data);
        while (exponent > 0) {
            if ((exponent & 1) == 1) {
                result = result.multiply(base, mod);
            }
            base = base.multiply(base, mod);
            exponent >>= 1;
        }
        return result;
    }
}

public class MatrixFastPow {
    /**
     * 使用矩阵快速幂计算斐波那契数列第n项
     * F(n) = F(n-1) + F(n-2)
     * [F(n)  ]   [1 1]^(n-1)   [F(1)]
     * [F(n-1)] = [1 0]       * [F(0)]
     */
    public static long fibonacci(long n, long mod) {
        if (n <= 1) return n;

        long[][] baseData = {{1, 1}, {1, 0}};
        Matrix base = new Matrix(baseData);
        Matrix result = base.pow(n - 1, mod);

        // F(1) = 1, F(0) = 0
        return result.data[0][0] % mod;
    }

    public static void main(String[] args) {
        long mod = 1_000_000_007L;
        System.out.println("F(10) = " + fibonacci(10, mod)); // 55
        System.out.println("F(50) = " + fibonacci(50, mod)); // 12586269025 % mod

        long start = System.currentTimeMillis();
        long f1000000 = fibonacci(1_000_000, mod);
        long end = System.currentTimeMillis();
        System.out.println("F(1000000) mod 1e9+7 = " + f1000000);
        System.out.println("耗时：" + (end - start) + " ms");
    }
}

扩展：模逆元计算

public class ModularInverse {
    /**
     * 使用费马小定理计算模逆元
     * 前提：modulus是质数，且a与modulus互质
     * a^(-1) ≡ a^(modulus-2) (mod modulus)
     */
    public static long modInverse(long a, long modulus) {
        if (modulus <= 1) {
            throw new IllegalArgumentException("modulus must be prime and > 1");
        }
        return FastModularExponentiation.fastPow(a, modulus - 2, modulus);
    }

    /**
     * 使用扩展欧几里得算法计算模逆元（适用于非质数模数）
     */
    public static long modInverseExtended(long a, long modulus) {
        long[] result = extendedGcd(a, modulus);
        long g = result[0], x = result[1];
        if (g != 1) {
            throw new ArithmeticException("Inverse does not exist");
        }
        return (x % modulus + modulus) % modulus;
    }

    private static long[] extendedGcd(long a, long b) {
        if (b == 0) {
            return new long[]{a, 1, 0};
        }
        long[] next = extendedGcd(b, a % b);
        long g = next[0], x1 = next[1], y1 = next[2];
        long x = y1;
        long y = x1 - (a / b) * y1;
        return new long[]{g, x, y};
    }
}

复杂度分析

实际应用

1. RSA加密：大数模幂运算是核心操作
2. 斐波那契数列：矩阵快速幂可在O(log n)内计算第n项
3. 组合数取模：预处理阶乘和逆元后，组合数计算变为O(1)
4. 图论：邻接矩阵的快速幂可计算路径数量

总结

快速幂取模展示了二进制拆分的强大威力。通过将指数转化为二进制位，把线性遍历转化为对数级操作。这一思想不仅适用于整数幂，还可以推广到矩阵、多项式等领域。掌握快速幂，是理解更高级算法（如矩阵快速幂、线性递推）的基础。