(SWEA c++)5607. [Professional] 조합

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXGKdbqczEDFAUo&categoryId=AWXGKdbqczEDFAUo&categoryType=CODE

SW Expert Academy

 

페르마의 소정리를 이용하여 조합을 구하는 문제.

페르마의 소정리는 아래 블로그를 통해 많은 도움을 얻었다.

m.blog.naver.com/PostView.nhn?blogId=1ilsang&logNo=221461026692&proxyReferer=https:%2F%2Fwww.google.com%2F

SWEA D3] 5607. [Professional] 조합 - 페르마의 소정리

DP를 이용하여 factorial을 모두 구해놓은 뒤 페르마의 소정리에 맞춰 답을 구하면 된다.

 

#include <iostream>
#include <vector>

using namespace std;
long long MOD = 1234567891;
long long fac[1000001] = {1, 1, };

long long fermat(int N, long long mod)
{
    if(mod == 0)
        return 1;
    
    long long tmp = fermat(N, mod / 2);
    long long ans = (tmp * tmp) % MOD;
    
    if(mod % 2 == 0)
        return ans;
    else
        return (N * ans) % MOD;
}

int main(void)
{
    int t;
    cin >> t;
    
    //Factorial 미리 구하기
    for(int i = 2; i <= 1000000; i++)
        fac[i] = (fac[i - 1] * i) % MOD;
    
    for(int i = 1; i <= t; i++)
    {
        int N, R;
        long long ans, a;
        
        cin >> N >> R;
        a = fermat((fac[R] * fac[N - R]) % MOD, MOD - 2);
        ans = (fac[N] * a) % MOD;
        cout << "#" << i << " " << ans << endl;
    }
    return 0;
}