UVA 369-组合|模块化算术|二进制幂运算

Question

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

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，但是由于您的代码以1000000007取模，因此结果将是1192052400 mod 1000000007 = 192052393，该值要小得多（不仅仅是小7）。

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