Day 171-Q5 — 2026-10-06 | 二項係数を合成数で割った余り（拡張 Lucas。素数冪ごとに p を抜いた階乗と Legendre の公式で求め、CRT で合わせる）

📋 コピーimport sys


def factorize(m):
    fs = []
    p = 2
    while p * p <= m:
        if m % p == 0:
            e = 0
            while m % p == 0:
                m //= p
                e += 1
            fs.append((p, e))
        p += 1
    if m > 1:
        fs.append((m, 1))
    return fs


def main():
    data = sys.stdin.buffer.read().split()
    t, M = int(data[0]), int(data[1])
    parts = []
    for p, e in factorize(M):
        pe = p ** e
        # tab[i] = (1..i のうち p で割れない数の積) mod p^e
        tab = [1] * (pe + 1)
        acc = 1
        for i in range(1, pe + 1):
            if i % p:
                acc = acc * i % pe
            tab[i] = acc
        # CRT の係数: x ≡ r (mod p^e), x ≡ 0 (mod M/p^e) となる x = r * coef
        other = M // pe
        coef = other * pow(other, -1, pe) % M if pe > 1 else 0
        parts.append((p, e, pe, tab, coef))

    out = []
    idx = 2
    for _ in range(t):
        n, k = int(data[idx]), int(data[idx + 1])
        idx += 2
        if k < 0 or k > n or M == 1:
            out.append(0)
            continue
        ans = 0
        r_ = n - k
        for p, e, pe, tab, coef in parts:
            # n!, k!, (n-k)! から p を除いた値を同じループで求める。同時に Legendre の公式で p の指数 cnt を数える
            #   x!_p = (±1)^(x // p^e) * tab[x % p^e] * (x // p)!_p
            num = den = 1
            cnt = 0
            flip = 0
            a, b, c = n, k, r_
            while a:
                num = num * tab[a % pe] % pe
                den = den * tab[b % pe] * tab[c % pe] % pe
                flip += a // pe - b // pe - c // pe
                a //= p; b //= p; c //= p
                cnt += a - b - c
            if cnt >= e:
                continue                       # p^e で割り切れる → この成分は 0
            if flip & 1 and tab[pe] != 1:      # p^e までの互いに素な数の積は ±1（p=2, e≥3 だけ +1）
                num = pe - num
            r = num * pow(den, -1, pe) * pow(p, cnt, pe) % pe
            ans = (ans + r * coef) % M
        out.append(ans)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()