Compute nCr%p Using Fermat Little Theorem in Java

2025年5月7日 | 阅读7分钟

使用费马小定理可以有效地处理计算组合数模素数 p 的任务。组合公式 ⁿC_r 表示从 n 个元素的集合中选择 r 个元素的总方法数。费马小定理提供了一种计算模逆的有效方法，从而简化了该过程。

组合公式为

ⁿC_r = n! / (r!(n - r)!)

它表示从 n 个元素的集合中选择 r 个元素的数量，其中

ⁿC_r 是二项式系数
n! 是 n 的阶乘，
r! 是 r 的阶乘，
(n-r)! 是 n-r 的阶乘。

示例 1

输入：n = 10, r = 2, p = 13

输出 6

解释

¹⁰C₂ = 10! / (2! * (10 - 2)!) = 10 * 9 / (2 * 1) = 45

45 % 13 = 6

示例 2

输入：n = 6, r = 2, p = 13

输出 2

解释

⁶C₂ = 6! / (2! * (6 - 2)!) = 6 * 5 / (2 * 1) = 15

15 % 13 = 2

费马小定理与模逆

费马小定理指出，如果 p 是一个素数，那么对于任何整数 a，a^p - a 的值都可以被 p 整除。使用模运算，这可以表示为

a^p = a (mod p)

例如，如果 a = 2 且 p = 7，则 2⁷ = 128，并且 128 - 2 = 7 × 18 是 7 的整数倍。

如果 a 不能被 p 整除，费马小定理指出 a^(p-1) - 1 可以被 p 整除。在模运算中，这写为

a^p-1 = 1 (mod p)

如果我们用 a^-1 乘以两边，则得到。

a^p-2 = a^-1 (mod p)

因此，我们可以将模逆找到为 ^p-2。

使用模运算预先计算阶乘

这种方法涉及预先计算所有小于等于 n 的值的模 p 的阶乘，这允许高效地计算组合数。通过存储阶乘值并使用费马小定理进行模逆计算，我们可以在预先计算后以常数时间计算 ⁿC_r mod p。

算法

步骤 1：检查 n<r：如果为真，则返回 0（因为从 n 个元素中选择 r 个是不可能的）。

步骤 2：检查 r=0：如果为真，则返回 1（因为 ⁿC₀=1）。

步骤 3：计算模 p 的阶乘：初始化一个阶乘数组 factorial[] 来存储从 1! 到 n! 的模 p 的阶乘值。

步骤 4：计算模逆：使用费马小定理，使用公式 a^(p-2) mod p 计算 factorial[r] 和 factorial[n-r] 的模逆。

步骤 5：应用组合公式：将 ⁿC_r mod p 计算为

ⁿC_r % p = (factorials[n] * inverseMod(factorials[r], p) * inverseMod(factorials[n - r], p)) % p

步骤 6：返回结果：打印 ⁿC_r mod p 的结果。

实施

文件名：CombinationModulo.java

import java.io.*;  // Import the necessary package for Input/Output
class CombinationModulo {  // Class definition for CombinationModulo
    // Function to compute base raised to the power exp modulo mod
    static int powerMod(int base, int exp, int mod) {  // Method to compute base^exp % mod
        int result = 1;  // Initialize result to 1, this will store the final result
        base = base % mod;  // Take the base modulo mod to reduce its size
        // Loop to compute base^exp % mod efficiently
        while (exp > 0) {  // Run until exponent becomes 0
            // If exp is odd, multiply the result by base
            if (exp % 2 == 1)  // Check if exp is odd
                result = (result * base) % mod;  // Update result with base modulo mod
            exp = exp >> 1;  // Right shift exp by 1 (equivalent to dividing by 2)
            base = (base * base) % mod;  // Square the base and take modulo
        }
        return result;  // Return the computed result (base^exp % mod)
    }
    // Function to compute the modular inverse of a number num modulo mod
    static int inverseMod(int num, int mod) {  // Method to compute modular inverse
        // Using Fermat's Little Theorem to find modular inverse
        return powerMod(num, mod - 2, mod);  // Compute num^(mod-2) % mod using powerMod method
    }
    // Function to compute nCr % mod using Fermat's Little Theorem
    static int calculateCombinationModulo(int n, int r, int mod) {  // Method to calculate nCr % mod
        // If n is less than r, combination is not possible
        if (n < r)  // Check if n is less than r
            return 0;  // Return 0 since nCr is not possible
        // Base case: if r is 0, nCr is 1
        if (r == 0)  // Check if r is 0
            return 1;  // Return 1 since nC0 is always 1
        // Initialize an array to store factorial values modulo mod
        int[] factorials = new int[n + 1];
        factorials[0] = 1;
        for (int i = 1; i <= n; i++)
            factorials[i] = factorials[i - 1] * i % mod;
        // Use the factorial values to calculate nCr % mod using the formula
        // nCr % mod = (n! * (r!)^(-1) * ((n-r)!)^(-1)) % mod
       return (factorials[n] * inverseMod(factorials[r], mod)  // Multiply n! with inverse of r!
                % mod * inverseMod(factorials[n - r], mod)  // Multiply by inverse of (n-r)!
                % mod)
            % mod;  // Take the result modulo mod and return it
    }
    // Main method to test the functionality
    public static void main(String[] args) {
        int n = 10, r = 2, mod = 13;
        int result = calculateCombinationModulo(n, r, mod);  // Compute nCr % mod
        // Print the result with a descriptive message
        System.out.println("The value of " + n + "C" + r + " modulo " + mod + " is: " + result);
    }
}   

输出

 
The value of ¹⁰C₂ modulo 13 is: 6

时间复杂度：O(n+log(mod))。

辅助空间复杂度：O(n)。

我们可以通过消除存储阶乘的单独数组的需要来优化空间复杂度。取而代之的是，我们可以在应用约简时直接乘以数字。

算法

步骤 1：通过重复平方基数和减半指数来高效地计算 base^exp % mod。

步骤 2：使用费马小定理查找 number^-1 % mod，即 number^(mod-2) % mod。

步骤 3：将两个数字模 mod 相乘，或通过计算分母的模逆来除。

步骤 4：计算 ⁿC_r：

如果 n < r，则返回 0。
如果 r == 0，则返回 1。
使用对称性：如果 r > n-r，则 **ⁿC_r** = ⁿC_(n-r)。
在模 mod 下，将分子项相乘，然后除以分母项。

步骤 5：调用函数计算 ⁿC_r % mod 并打印结果。

实施

文件名：CombinationCalculator.java

import java.util.*;  // Import the necessary package for utility classes
public class CombinationCalculator {  // Define the CombinationCalculator class
    // Function to compute (base^exp) % mod using modular exponentiation
    public static long modularExponentiation(long base, int exp, int mod) {  // Method to perform modular exponentiation
        long result = 1;  // Initialize result to 1, as base^0 = 1
        base = base % mod;  // Update base if it is more than or equal to mod to keep it within range
        // Loop to perform exponentiation in logarithmic time
        while (exp > 0) {  // Repeat until the exponent is greater than 0
            // If exponent is odd, multiply the result with base
            if ((exp & 1) == 1) {  // Check if the exponent is odd using bitwise AND with 1
                result = (result * base) % mod;  // Multiply result by base modulo mod
            }
            exp = exp >> 1;  // Halve the exponent (equivalent to exp = exp / 2) using right shift
            base = (base * base) % mod;  // Square the base and apply modulo
        }
        return result;  // Return the final result after exponentiation
    }
    // Function to calculate the modular inverse using Fermat's Little Theorem
    public static long calculateModInverse(long number, int mod) {  // Method to calculate modular inverse
        return modularExponentiation(number, mod - 2, mod);  // Using Fermat's Little Theorem: number^(mod-2) % mod
    }
    // Function to multiply two numbers under modulo
    public static long multiplyMod(long a, long b, int mod) {
        return (a * b) % mod;
    }
    // Function to divide two numbers under modulo
    public static long divideMod(long numerator, long denominator, int mod) {  // Method to divide numbers under modulo
        return multiplyMod(numerator, calculateModInverse(denominator, mod), mod);  // Apply modular inverse to denominator
    }
    // Function to compute nCr % p using Fermat's Little Theorem
    public static long computeCombination(long n, long r, int mod) {  // Method to calculate nCr modulo p
        if (n < r) {  // If n is less than r, combination is not possible
            return 0;  // Return 0 as nCr is undefined in this case
        }
        if (r == 0) {  // Base case: if r is 0, nCr is always 1
            return 1;  // Return 1 as nC0 = 1
        }
        if (n - r < r) {  // If n-r is less than r, use the symmetry property nCr = nC(n-r)
            return computeCombination(n, n - r, mod);  // Call the function with n and n-r
        }
        long result = 1;  // Initialize result to 1
        for (long i = r; i >= 1; i--) { 
            result = divideMod(multiplyMod(result, n - i + 1, mod), i, mod);
        }
        return result;  // Return the final result of nCr % mod
    }
    // Main method to test the functionality
    public static void main(String[] args) {
        int n = 10, r = 2, mod = 13; 
        System.out.println("Result of nCr % p is: " + computeCombination(n, r, mod));
    }
}   

输出

 
Result of ⁿC_r % p is: 6

时间复杂度：O(r⋅log(mod))

辅助空间复杂度: O(1)

下一主题什么是面向对象编程？

Compute nCr%p Using Fermat Little Theorem in Java

费马小定理与模逆

使用模运算预先计算阶乘

算法

实施

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Compute nCr%p Using Fermat Little Theorem in Java

费马小定理与模逆

使用模运算预先计算阶乘

算法

实施

算法

实施

相关帖子

Java 中 Future 和 Callable 接口的区别是什么

BreakIterator previous() method in Java with Examples

在 Java 中多次执行 main() 方法

Java EE vs Node.js

Java 中素数整数子数组的最大总和

Java Program to Count Number of Ways to Cover a Distance

Java Program to reverse tOGGLE each word in String

Java 中具有相同数字集的下一个更大的数字

Java 中的并集

Java 中将矩阵旋转 180 度

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器