UVA 369组合数问题排查：模运算与快速幂实现无法通过首测

Hey there! Let's figure out why your code isn't passing the first test case for UVA 369. The core issue here is a mismatch between what the problem requires and what your code is actually doing.

Key Mistakes in Your Code #

• Incorrect use of modular arithmetic: UVA 369 asks for the exact value of the combination ( C(n,m) ), not its remainder modulo ( 10^9+7 ). When the combination value exceeds ( 10^9+7 ) (which happens even for moderately sized ( n ), like ( C(100,50) ) is a 29-digit number), your code outputs a remainder instead of the actual result. This is almost certainly why the first test case fails.
• Unnecessary modulo operation: Your line fact((n-m) % M) is redundant—since the problem guarantees valid inputs where ( n \geq m \geq 0 ), ( n-m ) is non-negative and doesn't need a modulo here. This small issue signals confusion about when modular arithmetic should be applied.
• Overflow in factorial calculation: A long can only hold values up to ~9e18, but 21! already exceeds this limit (~5e19). For ( n \geq 21 ), your fact() function will overflow and return incorrect values, leading to wrong combination results.

Fix Approach: Calculate Exact Combinations Without BigInteger #

Since you want to avoid using BigInteger, we can compute ( C(n,m) ) via prime factorization followed by manual big integer multiplication (using an array to store digits and handle overflow). Here's the breakdown:

1. Compute the prime factor counts for ( n! ), ( m! ), and ( (n-m)! ).
2. Subtract the factor counts from ( m! ) and ( (n-m)! ) from those in ( n! ) to get the prime factorization of ( C(n,m) ).
3. Multiply these primes together using an array to store digits (to avoid overflow) and handle carry-over.

Corrected Code Example #

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = br.readLine()) != null) {
            line = line.trim().replaceAll("\\s+", " ");
            String[] parts = line.split(" ");
            long n = Long.parseLong(parts[0]);
            long m = Long.parseLong(parts[1]);
            if (n == 0 && m == 0) break;
            
            // Optimize: C(n,m) = C(n,n-m) to reduce computation
            m = Math.min(m, n - m);
            
            // Step 1: Count prime exponents for C(n,m)
            int[] exponents = new int[(int)n + 1];
            // Add exponents from n!
            for (int i = 2; i <= n; i++) {
                int temp = i;
                for (int p = 2; p * p <= temp; p++) {
                    while (temp % p == 0) {
                        exponents[p]++;
                        temp /= p;
                    }
                }
                if (temp > 1) exponents[temp]++;
            }
            // Subtract exponents from m!
            for (int i = 2; i <= m; i++) {
                int temp = i;
                for (int p = 2; p * p <= temp; p++) {
                    while (temp % p == 0) {
                        exponents[p]--;
                        temp /= p;
                    }
                }
                if (temp > 1) exponents[temp]--;
            }
            // Subtract exponents from (n-m)!
            long nm = n - m;
            for (int i = 2; i <= nm; i++) {
                int temp = i;
                for (int p = 2; p * p <= temp; p++) {
                    while (temp % p == 0) {
                        exponents[p]--;
                        temp /= p;
                    }
                }
                if (temp > 1) exponents[temp]--;
            }
            
            // Step 2: Multiply primes to get the result (big integer via array)
            int[] result = new int[200]; // Enough for 100! (~158 digits)
            result[0] = 1;
            int resultLength = 1;
            
            for (int p = 2; p <= n; p++) {
                while (exponents[p] > 0) {
                    int carry = 0;
                    // Multiply current result by p
                    for (int i = 0; i < resultLength; i++) {
                        int product = result[i] * p + carry;
                        result[i] = product % 10;
                        carry = product / 10;
                    }
                    // Handle remaining carry
                    while (carry > 0) {
                        result[resultLength] = carry % 10;
                        carry /= 10;
                        resultLength++;
                    }
                    exponents[p]--;
                }
            }
            
            // Convert result array to string (digits are stored in reverse order)
            StringBuilder sb = new StringBuilder();
            for (int i = resultLength - 1; i >= 0; i--) {
                sb.append(result[i]);
            }
            String ans = sb.toString();
            
            System.out.printf("%d things taken %d at a time is %s exactly%n", n, m, ans);
        }
    }
}

Explanation #

• Prime Factorization: We count how many times each prime appears in ( n! ), then subtract the counts from ( m! ) and ( (n-m)! ) to get the primes that make up ( C(n,m) ).
• Manual Big Integer Multiplication: We store digits in reverse order (least significant digit first) in an array, multiplying each prime into the result and handling carry-over to avoid overflow.
• Optimization: Using ( \text{Math.min}(m, n-m) ) reduces the number of operations since ( C(n,m) = C(n,n-m) ).

内容的提问来源于stack exchange，提问作者Abhishek Dasgupta