5607. 조합

$n^{p} \equiv n \left(\text{mod}\ p \right)$

N combination R의 값을 1234567891로 나눈 나머지를  출력.

즉, 우리에게 익숙한 nCr을 1234567891로 나눈 나머지를 출력하란 말이다.

nCr을 구하는 공식을 보면

이다.

하지만 나머지 연산은 나눗셈에 적용할 수 없다.

그래서 이 식을 곱셈 형태로 바꿔줘야 하는데 여기서 사용되는 것이

페르마의 소정리이다.

페르마의 소정리에 의해서

P를 1234567891이라고 하면

가 성립한다.

제곱의 경우는 분할 정복을 통해서 O(logP)의 시간복잡도 안에 해결할 수 있기 때문에 해결이 가능하다.

import java.util.Scanner;
 
public class Solution {
    static final int MOD = 1234567891;
    static long[] factorMOD;
    static int N, R;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt();
            R = sc.nextInt();
 
            factorMOD = new long[N + 1];
            factorMOD[1] = 1;
            for (int i = 2; i <= N; i++)
                factorMOD[i] = factorMOD[i - 1] * i % MOD;
 
            // A = N! ^ MOD %MOD
            long A = power(factorMOD[N], MOD) % MOD;
 
            // B = (R!*(N-R)!)^MOD-2 % MOD
            long B = power(factorMOD[R], MOD - 2) * power(factorMOD[N - R], MOD - 2) % MOD;
 
            long res = A * B % MOD;
 
            System.out.println("#" + tc + " " + res);
        }
    }
 
    static long power(long N, long x) {
        if (x == 1)
            return N % MOD;
        else {
            if (x % 2 == 1) {
                long tmp = power(N, (x - 1) / 2);
                return tmp * tmp % MOD * N % MOD;
            } else {
                long tmp = power(N, x / 2);
                return tmp * tmp % MOD;
            }
        }
    }
}