백준 14854 - 이항 계수 6

step 1

$142857=3^3*11*13*37$입니다. 만약 어떤 수 $n$에 대해 27,11,13,37로 나눈 나머지를 알 수 있다면 $n$을 142857로 나눈 나머지도 알 수 있습니다.

step 2

${n \choose k} = \frac{n!}{k!(n-k)!}$를 27로 나눈 나머지에 대해서만 생각해 봅시다.

 

만약 소인수분해를 했을 때 3이 3개 이상 나온다면 나머지는 0입니다.

이는 $O(log\ n)$에 해결할 수 있습니다.(https://codestudycafe.tistory.com/1)

 

어떤 수를 소인수분해를 하면 $2^{x_1}* 3^{x_2}* 5^{x_3} ..$ 식으로 나옵니다. 3이 몇 개 나오는지는 알았으니 나머지에 대해서만 생각하면 됩니다.

 

$f(x) = n!$을 3으로 나눌 수 없을 때 까지 나눈 값 $v$를 27으로 나눈 나머지라고 합시다

(14!=87178291200, 3으로 나눌 수 없을 때 까지 나누면 358758400. 이것을 27로 나눈 나머지는 4이므로 $f(14)=4$입니다.)

$f(n),f(m),f(n-m)$을 알 수 있다면 모듈러 나눗셈이 가능하므로 ${n \choose m}$을 27으로 나눈 나머지도 알 수 있습니다.(https://codestudycafe.tistory.com/3)

step 3

$n! = 1*2* \cdots *n$입니다. 여기서 3으로 나누어 떨어지지 않는 숫자들 먼저 곱해 줄 것입니다. 이 숫자들을 뽑아봅시다.

 

$1,2,4,5, \cdots, 25,26,28,29, \cdots $

 

저희의 목적은 $n! \bmod 27$을 구하는 것입니다. $xy \bmod n = ((x\bmod n)*(y\bmod n))\bmod n$이므로 각 숫자들에 $\bmod 27$을 취해줍니다.

 

$1, 2, 4, 5, \cdots , 25,26,1,2, \cdots$

그러면 같은 구간이 반복되는 것을 알 수 있습니다. 구간이 몇번 반복되는지는 $n/27$로 쉽게 구할 수 있습니다. 그럼 이 숫자들을 전부 곱한 값 역시 쉽게 구할 수 있습니다.

 

나머지 숫자들을 곱할 차례입니다. 이 숫자들을 뽑아보면

 

$3,6,9,12,15,18,21,\cdots $

 

입니다. 저희는 소인수 3의 개수들은 이미 구했으므로 각 숫자들을 3으로 나눠줍니다.

 

$1,2,3,4,5,6,7,8 \cdots$

 

이러면 처음으로 돌아왔습니다. 이제 재귀적으로 문제를 해결해 주면 됩니다.

 

11,13,37에 대해서도 같은 동작을 반복해 주면 이 문제를 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
int b[5] = { 0,27,11,13,37 };
int c[5], d[5], d2[5];
int calc[27][11][13][37];
int memo[100];
int countNum(int x, int y) {
    if (y == 27) y = 3;
    int cnt = 0;
    while (x != 0) {
        cnt += x / y;
        x /= y;
    }
    return cnt;
}
int pow(int x, int y, int m) {
    if (y == 0) return 1;
    if (y == 1) return x;
    int t = pow(x, y / 2, m);
    if (y % 2 == 0) return t * t % m;
    return (t * t) % m * x % m;
}
int get(int x, int m) {
    if (x == 0) return 1;
    int d, i;
    d = pow(memo[m], x / m, m);
    for (i = 1;i <= x % m;i++) {
        int ii = i;
        if (m == 27 && i % 3 == 0) continue;
        d *= ii; d %= m;
    }
    d *= get((m == 27 ? x / 3 : x / m), m); d %= m;
    return d;
}
int main() {
    int t, i, n, m, j;
    for (i = 1;i <= 142856;i++) {
        calc[i % 27][i % 11][i % 13][i % 37] = i;
    }
    for (i = 1;i <= 4;i++) {
        int bef = 1, now = 1, cnt = 1;
        for (j = 1;j < b[i];j++) {
            if (i == 1 && j % 3 == 0) continue;
            now *= j; now %= b[i];
        }
        memo[b[i]] = now;
    }
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &n, &m);
        if (m <= n / 2) m = n - m;
        if (n == m) { printf("1\n"); continue; }
        for (i = 1;i <= 4;i++) {
            c[i] = countNum(n, b[i]) - countNum(m, b[i]) - countNum(n - m, b[i]);
            d[i] = 0;
            d2[i] = 0;
        }
        if (c[1] >= 3 && c[2] >= 1 && c[3] >= 1 && c[4] >= 1) { printf("0\n"); continue; }
        for (i = 1;i <= 4;i++) {
            if (i == 1 && c[i] >= 3 || i != 1 && c[i] >= 1) continue;
            int v1 = get(n, b[i]);
            int v2 = get(m, b[i]);
            int v3 = get(n - m, b[i]);
            v2 *= v3; v2 %= b[i];
            v1 *= pow(v2, (i == 1 ? 17 : b[i] - 2), b[i]); v1 %= b[i];
            d[i] = v1;
        }
        if (c[1] == 1) d[1] *= 3;
        if (c[1] == 2) d[1] *= 9;
        d[1] %= 27;
        printf("%d\n", calc[d[1]][d[2]][d[3]][d[4]]);
    }
    return 0;
}

 

뤼카 정리

뤼카 정리를 쓰면 11,13,37에 대해서 더 쉽게 해결할 수 있는 듯 합니다(https://ko.wikipedia.org/wiki/%EB%A4%BC%EC%B9%B4%EC%9D%98_%EC%A0%95%EB%A6%AC). 27에 대해서 하는 법도 위키에 논문이 있는 것 같은데 저는 해석이 잘 안되네요.