UVA 369-组合 |模运算 |二进制指数

Question

我正在尝试使用模块化算术和二进制求幂来解决 uVa 的 369（组合）问题，而不是仅在 java 中使用 BigInteger class。我能够通过最后两个基本测试用例，但不能通过第一个测试用例。谁能解释我的代码哪里错了？

public class Main {
    static long M = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            String s = br.readLine();
            s = s.trim();
            s = s.replaceAll("\s{2,}", " ");
            String[] str = s.split(" ");
            long n = Long.parseLong(str[0]);
            long m = Long.parseLong(str[1]);
            if(n == 0 && m == 0) break;
            long a = fact(n); long b = fact((n-m) % M); long c = fact(m);
            long d = (b*c) % M;
            long ans = divide(a,d);
            System.out.println(n + " things taken " + m + " at a time is " + ans + " exactly");
        }
    }
    public static long fact(long N){
        long ans = 1;
        for(int i=1; i<=N; ++i)
            ans = (ans * i) % M;
        return ans;
    }
    public static long divide(long a, long b){
        return a * pow(b,M-2) % M;
    }
    public static long pow(long a, long b){
        long res = 1;
        while(b > 0){
            if(b % 2 == 1) res = (res*a) % M;
            a = (a*a) % M;
            b /=2;
        }
        return res;
    }
}

Answer 1

M 太小了。例如，对于输入 100 6，正确的结果是 1192052400，但由于您的代码工作 modulo 1000000007，结果将是 1192052400 mod 1000000007 = 192052393，它要小得多（不仅仅是7 小）。

使用 M = 0x7fffffff（也是质数）可能有效。

UVA 369-组合 |模运算 |二进制指数

UVA 369-Combinations | Modular Arithmetic | Binary Exponentiation

java

algorithm

modular-arithmetic