[SWEA] 3238 이항계수 구하기

출처: SWEA

Approach

뤼카의 정리와 페르마의 소정리를 적용하면 풀 수 있는 문제이다.

 

---

#include <stdio.h>
#define LL long long

const int MAX_N = 1e5 + 2;
int tc, TC;
LL ans, fact[MAX_N];
LL X, Y, n, r, p;

int main()
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (tc = 1; tc <= TC; ++tc)
    {
        scanf("%lld %lld %lld", &n, &r, &p);
        fact[0] = 1;
        for (int i = 1; i <= p; ++i)
        {
            fact[i] = (i * fact[i - 1]) % p;
        }

        ans = 1;

        // 뤼카의 정리
        while (r || n)
        {
            X = n % p; Y = r % p;

            if (Y > X)
            {
                ans = 0;
                break;
            }

            // 페르마의 소정리
            ans = (ans * fact[X]) % p;
            for (int i = 0; i < p - 2; i++)
            {
                ans = (ans * fact[X - Y] * fact[Y]) % p;
            }
            n /= p; r /= p;
        }
        ans %= p;
        printf("#%d %lld\n", tc, ans);
    }
    return 0;
}