Day 060-Q5 — Lucas定理 + Kummer定理

問題

整数 $N, K$（$0 \le K \le N \le 10^{18}$）と素数 $p$ が与えられる。以下の値を求めよ：

• $\binom{N}{K} \bmod p$（Lucas定理を使用）
• $\nu_p\left(\binom{N}{K}\right)$（二項係数の $p$ 進付値、Kummer定理を使用）

ここで $\nu_p(m)$ は $m$ が $p$ で割り切れる最大の指数（$p$-adic valuation）。

入出力例

3
10 3 3
1000000000000000000 500000000000000000 2
7 3 5

1 4
0 1
0 0

$\binom{10}{3} = 120 = 2^3 \cdot 3 \cdot 5$。mod 3 → $120 \equiv 0 \cdot 3^0 \cdot \dots$... 実際 $120 = 40 \cdot 3$, $\nu_3(120)=1$ ... 確認: $10_{10} = 101_3$, $3_{10} = 10_3$, $7_{10} = 21_3$。Lucas: $\binom{1}{0}\binom{0}{1}\binom{1}{0}$... 桁ごとに $n_i \ge k_i$? $k_i$ の桁 $(0,1,0)$, $n_i$ の桁 $(1,0,1)$: 2桁目 $k_i=1 > n_i=0$ → 0。Kummer: 数字和: $s_3(3)=1+0=1$, $s_3(7)=2+1=3$, $s_3(10)=1+0+1=2$。$\nu_3 = (1+3-2)/(3-1) = 2/2 = 1$。よって出力は $0\ 1$。

概念図: Lucas定理 と Kummer定理

ヒント（段階的開示）

def comb_small(n, k, p):
    if k < 0 or k > n: return 0
    if k == 0 or k == n: return 1
    k = min(k, n - k)
    num = 1; den = 1
    for i in range(k):
        num = num * ((n - i) % p) % p
        den = den * ((i + 1) % p) % p
    return num * pow(den, p - 2, p) % p

def lucas(n, k, p):
    if k < 0 or k > n: return 0
    result = 1
    while k > 0:
        ni = n % p; ki = k % p
        if ki > ni: return 0
        result = result * comb_small(ni, ki, p) % p
        n //= p; k //= p
    return result

def digit_sum(n, p):
    s = 0
    while n > 0: s += n % p; n //= p
    return s

def kummer(n, k, p):
    if k < 0 or k > n: return 0
    return (digit_sum(k, p) + digit_sum(n - k, p) - digit_sum(n, p)) // (p - 1)

模範解答 (Python)

コピーimport sys
input = sys.stdin.readline

def comb_small(n, k, p):
    """n, k < p での二項係数 mod p"""
    if k < 0 or k > n:
        return 0
    if k == 0 or k == n:
        return 1
    k = min(k, n - k)
    num = 1
    den = 1
    for i in range(k):
        num = num * ((n - i) % p) % p
        den = den * ((i + 1) % p) % p
    return num * pow(den, p - 2, p) % p

def lucas(n, k, p):
    """Lucas定理: C(n, k) mod p"""
    if k < 0 or k > n:
        return 0
    result = 1
    while k > 0:
        ni = n % p
        ki = k % p
        if ki > ni:
            return 0
        result = result * comb_small(ni, ki, p) % p
        n //= p
        k //= p
    return result

def digit_sum(n, p):
    """n の p 進数字和"""
    s = 0
    while n > 0:
        s += n % p
        n //= p
    return s

def kummer(n, k, p):
    """nu_p(C(n, k)): Kummer定理（数字和版）"""
    if k < 0 or k > n:
        return 0
    m = n - k
    return (digit_sum(k, p) + digit_sum(m, p) - digit_sum(n, p)) // (p - 1)

def main():
    T = int(input())
    out = []
    for _ in range(T):
        N, K, p = map(int, input().split())
        if K < 0 or K > N:
            out.append("0 0")
            continue
        c_mod = lucas(N, K, p)
        nu = kummer(N, K, p)
        out.append(f"{c_mod} {nu}")
    print('\n'.join(out))

main()

Step-by-Step 解説

Step 1: Lucas定理の証明概要

フェルマーの小定理より $(1+x)^p \equiv 1 + x^p \pmod{p}$（多項式として）。これを繰り返すと $(1+x)^n$ の係数が $p$ 進桁ごとに分解できる。$$\binom{n}{k} \equiv \prod_{i=0}^{\lfloor \log_p n \rfloor} \binom{n_i}{k_i} \pmod{p}$$

Step 2: Lucas定理の計算

$N \le 10^{18}$、$p \ge 2$ なので桁数は最大 $\log_p N \le 60$ 桁。各桁の comb_small(ni, ki, p) は $O(\min(k_i, n_i-k_i))$。

Step 3: Kummer定理の証明概要

Legendre公式: $\nu_p(n!) = \frac{n - s_p(n)}{p-1}$。これを展開： $$\nu_p\binom{n}{k} = \nu_p(n!) - \nu_p(k!) - \nu_p((n-k)!) = \frac{s_p(k) + s_p(n-k) - s_p(n)}{p-1}$$

Step 4: 整数論的直観

Kummer定理の別解釈：$k$ と $n-k$ を $p$ 進数で足して $n$ を得る際の繰り上がり回数 = $\nu_p\binom{n}{k}$。繰り上がりが多いほど二項係数が $p$ で多く割れる。

Step 5: 計算量

各クエリ $O(\log_p N)$。$T = 10^5$、$\log_2(10^{18}) \approx 60$。全体 $O(T \log N)$。

よくあるミス

次のステップ

発展問題: Andrew Granville の一般化 Lucas 定理（$p^e$ の場合）を実装せよ。$\binom{n}{k} \bmod p^e$ を求めるには Granville's theorem または Lifting the Exponent Lemma が必要になる。

自己評価