计算器

GitHub跳转原题关系图返回列表

三问合一:快速幂求 y^z mod P;扩展 BSGS 求 y^x≡z (mod P) 的最小非负解;扩展 Lucas 拆质数幂加 CRT 求 C(z,y) mod P。

OJ: roj

题目 ID: 1806

难度:提高+/省选-

标签:数学数论快速幂BSGS扩展卢卡斯中国剩余定理python

创建: 2026-10-08 04:23

更新: 2026-10-08 04:23

形式化题目

每次询问给出四个整数 type,y,z,Ptype, y, z, P(P⩾1P \geqslant 1),按 typetype 回答:

type=1:yz mod P;type=2:满足 yx≡z(modP) 的最小非负整数 x(不存在则输出 Math Error);type=3:(zy) mod P(即题面 Czy,z 中取 y 的组合数). \begin{aligned} type = 1:&\quad y^z \bmod P;\\[2pt] type = 2:&\quad \text{满足 } y^x \equiv z \pmod P \text{ 的最小非负整数 } x \text{(不存在则输出 \texttt{Math Error})};\\[2pt] type = 3:&\quad \binom{z}{y} \bmod P \quad (\text{即题面 } C_z^y \text{,}z \text{ 中取 } y \text{ 的组合数}). \end{aligned}

约束:y,z,P⩽109y, z, P \leqslant 10^9,询问总数 N⩽500N \leqslant 500;PP 不保证是质数,但若 PP 为合数, 把 PP 分解为 ∏ipiai\prod_i p_i^{a_i} 后保证每个质数幂 piai⩽105p_i^{a_i} \leqslant 10^5。时限 1 s,内存 256 MB。

三问都不含任何交互,可以各自独立求解,最后把答案按输入顺序输出。

解法总览

三问共用同一份程序,但用的是三套互不相干的技巧,瓶颈也各不相同,所以分开成三节:

询问 朴素瓶颈 正解技巧 单次复杂度
type=1type=1 乘 zz 次,O(z)O(z),z⩽109z \leqslant 10^9 二进制拆分(快速幂) O(log⁡z)O(\log z)
type=2type=2 逐 xx 试到出现循环,O(P)O(P) 折半枚举(扩展 BSGS) O(P)O(\sqrt P)
type=3type=3 阶乘数值爆炸;PP 非质数时逆元可能不存在 扩展 Lucas + CRT O ⁣(∑ipiai+log⁡P)O\!\big(\sum_i p_i^{a_i} + \log P\big)

问题一:yz mod Py^z \bmod P

思路

把指数 zz 按二进制拆开。设 z=∑k2kbkz = \sum_k 2^k b_k,则

yz=∏k: bk=1y2k.y^z = \prod_{k:\, b_k = 1} y^{2^k}.

而 y2k+1=(y2k)2y^{2^{k+1}} = \big(y^{2^k}\big)^2,所以只要不断把底数自乘,就能在 O(log⁡z)O(\log z) 内 凑出全部需要的次幂。实现上就是标准的平方取幂:从低位往高位扫 zz,当前位为 1 时把底数 乘进答案,每一位都把底数平方。

边界要注意 z=0z = 0 时答案为 1 mod P1 \bmod P(包括 P=1P = 1 时输出 00),以及所有乘法都在 101810^{18} 量级,必须全程 64 位整数。

复杂度

单次 O(log⁡z)O(\log z) 时间、O(1)O(1) 空间。

问题二:yx≡z(modP)y^x \equiv z \pmod P 的最小非负解

思路

先处理 yy 与 PP 不互质的情形。 此时 yy 关于 PP 没有逆元,直接套 BSGS 会在"乘逆元" 这一步崩掉。记 d=gcd⁡(y,P)d = \gcd(y, P):当 x⩾1x \geqslant 1 时 d∣yxd \mid y^x,所以必须有 d∣zd \mid z, 否则无解;若 d∣zd \mid z,把同余式两边和模数同时除以 dd,并记下"已经提出来的系数"

k←k⋅yd,P←Pd,z←zd,cnt←cnt+1,k \leftarrow k \cdot \frac{y}{d}, \qquad P \leftarrow \frac{P}{d}, \qquad z \leftarrow \frac{z}{d}, \qquad cnt \leftarrow cnt + 1,

其中 kk 按新的(更小的)模数取模。反复做直到 gcd⁡(y,P)=1\gcd(y, P) = 1,此时原方程等价于

k⋅y x−cnt≡z(modP).k \cdot y^{\,x - cnt} \equiv z \pmod P .

每轮消因子后立刻检查 k≡z(modP)k \equiv z \pmod P 是否成立:若成立说明 x=cntx = cnt 已经是解, 而且它是当前能找到的最小候选,可以直接返回。kk 的初值是 11,所以 x=0x = 0 的情形 (即 z≡1z \equiv 1)必须在最开始单独判掉,否则消因子会改写 zz 和 PP 而错过它。

再处理 gcd⁡(y,P)=1\gcd(y, P) = 1 的情形,用 BSGS。 取 m=⌈P⌉m = \lceil \sqrt P \rceil,把未知指数写成 x−cnt=i⋅m−jx - cnt = i \cdot m - j(0⩽j⩽m0 \leqslant j \leqslant m,1⩽i⩽m1 \leqslant i \leqslant m),则方程变成

k⋅(ym)i≡z⋅y j(modP).k \cdot (y^m)^i \equiv z \cdot y^{\,j} \pmod P .

右边只依赖 jj,只有 m+1m + 1 种取值,所以先把所有 z⋅yj mod Pz \cdot y^j \bmod P 存进一张哈希表 (记为"小步");左边只依赖 ii,枚举 ii 并查表即可。两侧各 O(P)O(\sqrt P) 次乘法, 把 O(P)O(P) 的枚举压到 O(P)O(\sqrt P)。

哈希表里同值必须保留最大的 jj。 yy 的阶可能小于 mm,于是同一个值会被多个 jj 命中。 由 x=im−j+cntx = i m - j + cnt 可知,同值时 jj 越大 xx 越小,所以插入时直接覆盖成更大的 jj (小步按 jj 升序插入,后写覆盖先写,天然保留最大 jj)。这是本题最容易写错的一处: 若保留最小的 jj,答案会偏大甚至超过阶而判成无解。

P=1P = 1 时所有同余式恒成立,最小解是 x=0x = 0,需要在一开始就返回。

复杂度

消因子至多 O(log⁡P)O(\log P) 轮,每轮 O(log⁡P)O(\log P);BSGS 建表与枚举各 O(P)O(\sqrt P)。 单次时间 O(P)O(\sqrt P),空间 O(P)O(\sqrt P)(不超过约 3.2×1043.2 \times 10^4 个键值对)。

问题三:(zy) mod P\binom{z}{y} \bmod P

思路

PP 不保证是质数,所以既不能直接用阶乘除阶乘(数值太大),也不能直接对分母求逆元 (分母可能与 PP 不互质)。两层拆解:

第一层:把 PP 拆成质数幂再用 CRT 合并。 设 P=∏ipiaiP = \prod_i p_i^{a_i},各 piaip_i^{a_i} 两两互质。分别求出 (zy) mod piai\binom{z}{y} \bmod p_i^{a_i} 后,用中国剩余定理合并:

x←x+M⋅((ri−x) mod piai)⋅(M−1 mod piai),M←M⋅piai,x \leftarrow x + M \cdot \Big( (r_i - x) \bmod p_i^{a_i} \Big) \cdot \big(M^{-1} \bmod p_i^{a_i}\big), \qquad M \leftarrow M \cdot p_i^{a_i},

其中 MM 是已合并部分的模数(始终与下一个 piaip_i^{a_i} 互质,逆元存在)。

第二层:对单个质数幂 pap^a 求 (zy)\binom{z}{y},即扩展 Lucas。 关键是把阶乘里所有 pp 因子单独剥离出来。定义 f(n)f(n) 为 n!n! 去掉全部质因子 pp 之后模 pap^a 的值。在模 pap^a 意义下,与 pp 互质的数之乘积以 pap^a 为周期,于是

f(n)=(∏1⩽i⩽pa, p∤ii)⌊n/pa⌋⋅∏1⩽i⩽n mod pa, p∤ii⋅f(⌊n/p⌋)(modpa),f(n) = \Big(\prod_{1 \leqslant i \leqslant p^a,\, p \nmid i} i\Big)^{\lfloor n/p^a \rfloor} \cdot \prod_{1 \leqslant i \leqslant n \bmod p^a,\, p \nmid i} i \cdot f(\lfloor n/p \rfloor) \pmod{p^a},

最后一项来自把所有 pp 的倍数各提出一个 pp 之后剩下的 (⌊n/p⌋)!(\lfloor n/p \rfloor)!。 用长度为 pa+1p^a + 1 的前缀积表把两个乘积段落压成 O(1)O(1)(题面保证 pa⩽105p^a \leqslant 10^5, 表很短)。n!n! 中 pp 的个数用 Legendre 公式算:

vp(n!)=∑k⩾1⌊npk⌋.v_p(n!) = \sum_{k \geqslant 1} \Big\lfloor \frac{n}{p^k} \Big\rfloor .

令 e=vp(z!)−vp(y!)−vp((z−y)!)e = v_p(z!) - v_p(y!) - v_p((z-y)!),它就是组合数中因子 pp 的净次数。于是

(zy)≡pe⋅f(z)⋅f(y)−1⋅f(z−y)−1(modpa).\binom{z}{y} \equiv p^{e} \cdot f(z) \cdot f(y)^{-1} \cdot f(z-y)^{-1} \pmod{p^a} .

此时 f(⋅)f(\cdot) 都与 pp 互质,逆元用扩展欧几里得求,一定存在。 若 e⩾ae \geqslant a 则 pe≡0(modpa)p^e \equiv 0 \pmod{p^a},组合数直接是 00,不必再算逆元。

边界:P=1P = 1 输出 00;y>zy > z 输出 00;y=0y = 0 或 y=zy = z 输出 1 mod P1 \bmod P。 PP 本身是质数(P⩽109P \leqslant 10^9)时表开不下,改用 Lucas 定理逐位计算: 把 z,yz, y 写成 PP 进制,逐位求小组合数相乘,某一位上 yi>ziy_i > z_i 则整体为 00; 小组合数里 a<Pa < P,分母 k!k! 与 PP 互质,用费马小定理求逆元即可。

复杂度

分解 PP 为 O(P)O(\sqrt P);对每个质数幂,ff 的递归层数是 O(log⁡pz)O(\log_p z), 建表 O(pa)O(p^a);CRT 合并 O(ω(P)log⁡P)O(\omega(P) \log P),其中不同质因子数 ω(P)⩽9\omega(P) \leqslant 9。 单次时间 O ⁣(∑ipiai+log⁡P)O\!\big(\sum_i p_i^{a_i} + \log P\big),空间 O(max⁡ipiai)O(\max_i p_i^{a_i})。

完整程序

三问写在同一份程序里,按 typetype 分派后顺序输出。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-02-14 09:30
# update_at: 2026-02-14 09:30

import sys
from functools import cache
from math import gcd, isqrt

NO_SOLUTION = "Math Error"  # 类型 2 无解时的输出(题目要求的固定字符串)

type BabySteps = dict[int, int]  # 值 -> 该值下最大的小步指数 j
type FactorPowers = list[tuple[int, int]]  # [(p, p^a), ...]:不同质因子各自聚成一项


def exgcd(a: int, b: int) -> tuple[int, int, int]:
    """返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)。"""
    if b == 0:
        return a, 1, 0
    g, x, y = exgcd(b, a % b)
    return g, y, x - a // b * y


def inv_mod(a: int, m: int) -> int:
    """求 a 在模 m 下的逆元,要求 gcd(a, m) = 1。"""
    return exgcd(a % m, m)[1] % m


def pow_mod(a: int, b: int, m: int) -> int:
    """快速幂:a^b mod m(Python 内置 pow 已同阶,这里直接透传以对齐 C++)。"""
    return pow(a, b, m)


def log_discrete(a: int, b: int, p: int) -> int:
    """扩展 BSGS:求 a^x ≡ b (mod p) 的最小非负整数 x,无解返回 -1。"""
    a %= p
    b %= p
    if p == 1:
        return 0  # 模 1 下一切同余成立,最小 x = 0
    if b == 1:
        return 0  # a^0 = 1
    # 消去 gcd(a, p):d = gcd(a,p) 必须整除 b,否则无解;之后 p ← p/d, b ← b/d
    cnt, k = 0, 1
    d = gcd(a, p)
    while d != 1:
        if b % d:
            return -1
        b //= d
        p //= d
        k = k * (a // d) % p
        cnt += 1
        if b == k:
            return cnt  # x = cnt 已成立,且它是最小的
        d = gcd(a, p)
    if p == 1:
        return cnt
    # 标准 BSGS:令 x - cnt = i*m - j,则 k*(a^m)^i ≡ b*a^j (mod p)
    m = isqrt(p) + 1
    baby: BabySteps = {}
    cur = b
    for j in range(m + 1):
        baby[cur] = j  # 同值覆盖成更大的 j,保证 i*m - j 最小
        cur = cur * a % p
    base = pow_mod(a, m, p)
    cur = k
    for i in range(1, m + 1):
        cur = cur * base % p
        if cur in baby:
            return i * m - baby[cur] + cnt
    return -1


def factor_prime_powers(n: int) -> FactorPowers:
    """把 n 分解成 [(p, p^a), ...],同一个质数的幂聚成一项。"""
    fac: FactorPowers = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            pk = 1
            while n % d == 0:
                n //= d
                pk *= d
            fac.append((d, pk))
        d += 1
    if n > 1:
        fac.append((n, n))
    return fac


def count_p_in_fact(n: int, p: int) -> int:
    """n! 中质因子 p 的个数(Legendre 公式)。"""
    s = 0
    while n:
        n //= p
        s += n
    return s


@cache
def coprime_cycle(p: int, pk: int) -> int:
    """一个完整周期内所有与 p 互质之数的乘积 mod p^a,即 ∏_{1≤i≤p^a, p∤i} i。"""
    cycle = 1
    for i in range(1, pk + 1):
        if i % p:
            cycle = cycle * i % pk
    return cycle


def fac_without_p(n: int, p: int, pk: int) -> int:
    """n! 剔除全部质因子 p 后模 p^a 的值:整周期用幂、余项直接乘,再递归 ⌊n/p⌋!。"""
    res = 1
    while n:
        res = res * pow(coprime_cycle(p, pk), n // pk, pk) % pk
        partial = 1
        for i in range(1, n % pk + 1):
            if i % p:
                partial = partial * i % pk
        res = res * partial % pk
        n //= p
    return res


def comb_mod_prime_power(n: int, m: int, p: int, pk: int) -> int:
    """C(n, m) mod p^a(p 为质数):提出全部 p 因子后,剩余部分与 p^a 互质可求逆元。"""
    if m < 0 or m > n:
        return 0
    e = count_p_in_fact(n, p) - count_p_in_fact(m, p) - count_p_in_fact(n - m, p)
    if e < 0 or pow(p, e, pk) == 0:
        return 0  # e ≥ a,组合数被 p^a 整除
    res = pow(p, e, pk) * fac_without_p(n, p, pk) % pk
    res = res * inv_mod(fac_without_p(m, p, pk), pk) % pk
    return res * inv_mod(fac_without_p(n - m, p, pk), pk) % pk


def fac_small(a: int, k: int, p: int) -> int:
    """C(a, k) mod p,其中 0 ≤ k ≤ a < p(此时 k! 与 p 互质,可以直接求逆元)。"""
    num = den = 1
    for j in range(1, k + 1):
        num = num * (a - k + j) % p
        den = den * j % p
    return num * pow(den, p - 2, p) % p


def lucas_prime(n: int, m: int, p: int) -> int:
    """C(n, m) mod p(p 为质数),Lucas 定理逐位算小组合数。"""
    if m < 0 or m > n:
        return 0
    res = 1
    while n or m:
        a, b = n % p, m % p
        if b > a:
            return 0  # 该位小组合数为 0
        res = res * fac_small(a, min(b, a - b), p) % p  # 用对称性少乘一半
        n //= p
        m //= p
    return res


def comb_mod(y: int, z: int, P: int) -> int:
    """C(z, y) mod P(P 可为合数):逐质数幂算 + CRT 合并。"""
    n, m = z, y
    if P == 1:
        return 0
    if m < 0 or m > n:
        return 0
    if m == 0 or m == n:
        return 1 % P
    fac = factor_prime_powers(P)
    if len(fac) == 1 and fac[0][0] == P:
        return lucas_prime(n, m, P)  # P 本身是质数
    x, M = 0, 1
    for p, pk in fac:
        r = comb_mod_prime_power(n, m, p, pk)
        t = (r - x) % pk * inv_mod(M % pk, pk) % pk
        x = (x + M * t) % (M * pk)
        M *= pk
    return x


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    N = next(data)
    for _ in range(N):
        op, y, z, P = next(data), next(data), next(data), next(data)
        if op == 1:
            out.append(str(pow_mod(y, z, P)))
        elif op == 2:
            r = log_discrete(y, z, P)
            out.append(NO_SOLUTION if r < 0 else str(r))
        else:
            out.append(str(comb_mod(y, z, P)))
    print("\n".join(out))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-02-14 09:30
 * update_at: 2026-02-14 09:30
 */
// 一本通 1806「计算器」:三个数论子问题合在一份程序里。
//   type 1: y^z mod P                    —— 快速幂           O(log z)
//   type 2: y^x ≡ z (mod P) 的最小非负 x —— 扩展 BSGS        O(sqrt(P))
//   type 3: C(z,y) mod P                 —— 扩展 Lucas + CRT O(sum p_i^a_i * log)
// 题面保证 P 为合数时每个质因数幂 p_i^a_i ≤ 1e5,所以 exLucas 的前缀积表很短;
// 质数 P 走 Lucas 定理(逐位直接算小组合数),不需要开 O(P) 的表。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll PK_LIMIT = 1000000; // 前缀积表规模上限(合数的 p^a 按题面保证 ≤ 1e5)

ll pre[PK_LIMIT + 1]; // pre[i] = ∏_{1≤j≤i, p∤j} j mod p^a,只为当前的 (p, p^a) 重建

// 快速幂:返回 a^b mod m
ll qpow(ll a, ll b, ll m) {
    if (m == 1) return 0;
    a %= m;
    ll res = 1 % m;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

// 扩展欧几里得:返回 gcd(a,b),并顺带解出 a*x + b*y = gcd(a,b)
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

// 求 a 在模 m 下的逆元,要求 gcd(a,m)=1 且 m ≥ 2
ll inv_mod(ll a, ll m) {
    ll x, y;
    exgcd(a % m, m, x, y);
    return ((x % m) + m) % m;
}

/* ---------------- type 1:快速幂 ---------------- */

ll solve_pow(ll y, ll z, ll P) { return qpow(y, z, P); }

/* ---------------- type 2:扩展 BSGS ---------------- */

struct BabyStep {
    ll val; // 值 z * y^j mod p
    ll j;   // 对应的指数 j;同一 val 下保留最大的 j,才能让 x = i*m - j 最小
};

vector<BabyStep> baby; // 小步表:排序后二分查找

bool baby_cmp(const BabyStep &u, const BabyStep &v) {
    if (u.val != v.val) return u.val < v.val;
    return u.j < v.j; // 同值按 j 升序,方便把每段的最大 j 传播给整段
}

// 求 a^x ≡ b (mod p) 的最小非负整数 x,无解返回 -1
ll exbsgs(ll a, ll b, ll p) {
    a %= p;
    b %= p;
    if (p == 1) return 0; // 模 1 时一切同余都成立,最小 x = 0
    if (b == 1) return 0; // a^0 = 1
    // 第一步:消去 gcd(a,p) 的公共因子,把问题化为 gcd(a,p)=1 的情形。
    // 若 d = gcd(a,p),则 d | a^x 必须 d | b,否则无解;两边同除 d 后
    // p ← p/d, b ← b/d, k ← k*(a/d)(k 是"已经提出来的那部分系数")。
    ll cnt = 0;
    ll k = 1;
    ll d = __gcd(a, p);
    while (d != 1) {
        if (b % d != 0) return -1;
        b /= d;
        p /= d;
        k = k * (a / d) % p;
        cnt++;
        if (b == k) return cnt; // x = cnt 时 k*a^0 ≡ b 已成立,且 cnt 是最小的
        d = __gcd(a, p);
    }
    if (p == 1) return cnt; // 化到模 1:任何 x ≥ cnt 都是解,最小取 cnt
    // 第二步:标准 BSGS。设 x - cnt = y = i*m - j,则 k*(a^m)^i ≡ b*a^j (mod p)。
    ll m = (ll)ceil(sqrt((double)p)) + 1;
    baby.clear();
    baby.reserve((size_t)m + 1);
    ll cur = b;
    for (ll j = 0; j <= m; j++) {
        baby.push_back(BabyStep{cur, j});
        cur = cur * a % p;
    }
    sort(baby.begin(), baby.end(), baby_cmp);
    ll sz = (ll)baby.size();
    for (ll i = sz - 2; i >= 0; i--) { // 同值段内把最大的 j 向后传播
        if (baby[i].val == baby[i + 1].val) baby[i].j = baby[i + 1].j;
    }
    ll base = qpow(a, m, p);
    cur = k;
    for (ll i = 1; i <= m; i++) {
        cur = cur * base % p;
        ll lo = 0, hi = sz - 1, pos = -1;
        while (lo <= hi) {
            ll mid = (lo + hi) >> 1;
            if (baby[mid].val == cur) {
                pos = mid;
                break;
            }
            if (baby[mid].val < cur) lo = mid + 1;
            else hi = mid - 1;
        }
        if (pos >= 0) return i * m - baby[pos].j + cnt;
    }
    return -1;
}

/* ---------------- type 3:扩展 Lucas ---------------- */

// 建立前缀积表:pre[i] = ∏_{1≤j≤i, p∤j} j mod p^a(pre[0] 是空积 1)
void build_table(ll p, ll pk) {
    pre[0] = 1 % pk;
    for (ll i = 1; i <= pk; i++) {
        ll v = (i % p == 0) ? 1 : i; // 跳过 p 的倍数(它的 p 因子由 count_p_in_fact 单独统计)
        pre[i] = pre[i - 1] * v % pk;
    }
}

// n! 剔除全部质因子 p 之后模 p^a 的值(有前缀积表版本)
ll fac_without_p(ll n, ll p, ll pk) {
    ll res = 1;
    while (n > 0) {
        res = res * qpow(pre[pk], n / pk, pk) % pk; // 完整周期的重复部分
        res = res * pre[n % pk] % pk;               // 不完整周期
        n /= p;                                     // 递归处理 ⌊n/p⌋!
    }
    return res;
}

// n! 剔除全部质因子 p 之后模 p^a 的值(无表兜底,O(p^a) 每次;题面保证用不到)
ll fac_without_p_slow(ll n, ll p, ll pk) {
    if (n == 0) return 1;
    ll cycle = 1;
    for (ll i = 1; i <= pk; i++)
        if (i % p != 0) cycle = cycle * i % pk; // 一个完整周期的乘积
    ll res = qpow(cycle, n / pk, pk);
    for (ll i = 1; i <= n % pk; i++)
        if (i % p != 0) res = res * i % pk;
    return res * fac_without_p_slow(n / p, p, pk) % pk;
}

// n! 中质因子 p 的个数(Legendre 公式)
ll count_p_in_fact(ll n, ll p) {
    ll s = 0;
    while (n > 0) {
        n /= p;
        s += n;
    }
    return s;
}

// C(n,m) mod p^a(p 为质数,p^a 为模数);调用前若 p^a ≤ PK_LIMIT 需先 build_table
ll comb_mod_prime_power(ll n, ll m, ll p, ll pk) {
    if (m < 0 || m > n) return 0;
    ll e = count_p_in_fact(n, p) - count_p_in_fact(m, p) - count_p_in_fact(n - m, p);
    if (e < 0) return 0;
    if (qpow(p, e, pk) == 0) return 0; // e ≥ a 时组合数被 p^a 整除,余 0
    ll res = qpow(p, e, pk);
    if (pk <= PK_LIMIT) {
        res = res * fac_without_p(n, p, pk) % pk;
        res = res * inv_mod(fac_without_p(m, p, pk), pk) % pk;
        res = res * inv_mod(fac_without_p(n - m, p, pk), pk) % pk;
    } else {
        res = res * fac_without_p_slow(n, p, pk) % pk;
        res = res * inv_mod(fac_without_p_slow(m, p, pk), pk) % pk;
        res = res * inv_mod(fac_without_p_slow(n - m, p, pk), pk) % pk;
    }
    return res;
}

// C(n,m) mod p(p 为质数),Lucas 定理 + 逐位直接算小组合数
ll lucas_prime(ll n, ll m, ll p) {
    if (m < 0 || m > n) return 0;
    ll res = 1;
    while (n > 0 || m > 0) {
        ll a = n % p;
        ll b = m % p;
        if (b > a) return 0;   // 该位上 C(a,b) = 0,整体为 0
        ll bb = min(b, a - b); // 用对称性少乘一半
        ll num = 1, den = 1;
        for (ll j = 1; j <= bb; j++) {
            num = num * ((a - bb + j) % p) % p;
            den = den * (j % p) % p;
        }
        res = res * num % p;
        if (den != 1) res = res * qpow(den, p - 2, p) % p; // p 是质数,费马小定理求逆元
        n /= p;
        m /= p;
    }
    return res;
}

struct PrimePower {
    ll p;  // 质因子
    ll pk; // 对应的幂 p^a
};

// C(z,y) mod P,P 不保证是质数(C(z,y) 表示 z 中取 y)
ll solve_comb(ll y, ll z, ll P) {
    ll n = z, m = y;
    if (P == 1) return 0;        // 模 1 恒为 0
    if (m < 0 || m > n) return 0;
    if (m == 0 || m == n) return 1 % P;
    // 分解 P = ∏ p_i^a_i
    PrimePower fac[64]; // 1e9 内的不同质因子最多 9 个,64 足够
    ll fac_cnt = 0;
    ll tmp = P;
    for (ll d = 2; d * d <= tmp; d++) {
        if (tmp % d == 0) {
            ll pk = 1;
            while (tmp % d == 0) {
                tmp /= d;
                pk *= d;
            }
            fac[fac_cnt].p = d;
            fac[fac_cnt].pk = pk;
            fac_cnt++;
        }
    }
    if (tmp > 1) {
        fac[fac_cnt].p = tmp;
        fac[fac_cnt].pk = tmp;
        fac_cnt++;
    }
    if (fac_cnt == 1 && fac[0].p == P) return lucas_prime(n, m, P); // P 本身是质数
    // 一般情形:每个质数幂算一个余数,再用 CRT 合并(各 p_i^a_i 两两互质)
    ll x = 0, M = 1;
    for (ll i = 0; i < fac_cnt; i++) {
        ll p = fac[i].p, pk = fac[i].pk;
        if (pk <= PK_LIMIT) build_table(p, pk);
        ll r = comb_mod_prime_power(n, m, p, pk);
        ll t = ((r - x) % pk + pk) % pk * inv_mod(M % pk, pk) % pk;
        x = (x + M * t) % (M * pk); // 把 x ≡ r (mod pk) 合并到当前模 M 上
        M *= pk;
    }
    return x;
}

/* ---------------- main ---------------- */

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    if (!(cin >> N)) return 0;
    string out;
    out.reserve((size_t)N * 12);
    while (N--) {
        ll op, y, z, P;
        cin >> op >> y >> z >> P;
        if (op == 1) {
            out += to_string(solve_pow(y, z, P));
        } else if (op == 2) {
            ll r = exbsgs(y, z, P);
            if (r < 0) out += "Math Error";
            else out += to_string(r);
        } else {
            out += to_string(solve_comb(y, z, P));
        }
        out += '\n';
    }
    fwrite(out.data(), 1, out.size(), stdout);
    return 0;
}

Python 版与 C++ 版是同一套算法:快速幂直接用内置 pow(同样是平方取幂,O(log⁡z)O(\log z)); BSGS 的小步表用 dict 存"值 → 最大的 jj";扩展 Lucas 用 @cache 缓存单个周期内 与 pp 互质之数的乘积。算法阶数与 C++ 完全一致,没有为了速度降级成暴力。 实测在随仓 10 个数据点上 C++ 全部 0.01∼0.10.01 \sim 0.1 s,Python 0.01 s(type=1,2type=1,2 点) 到 0.8 s(problem10,150 组混合顶格)。

复杂度

记 ω(P)\omega(P) 为 PP 的不同质因子个数,pk(P)=max⁡ipiai\mathrm{pk}(P) = \max_i p_i^{a_i}:

  • 时间:type=1type=1 为 O(log⁡z)O(\log z);type=2type=2 为 O(P)O(\sqrt P); type=3type=3 为 O(P+∑ipiailog⁡pz+ω(P)log⁡P)O(\sqrt P + \sum_i p_i^{a_i} \log_p z + \omega(P) \log P)。
  • 空间:type=2type=2 的哈希表 O(P)O(\sqrt P)(约 3.2×1043.2 \times 10^4 项), type=3type=3 的前缀积表 O(pk(P))O(\mathrm{pk}(P))(⩽105\leqslant 10^5)。
  • 整体远低于 1 s / 256 MB 的限制。

总结

三个子问题都靠"换一个坐标系"把规模降下来:快速幂换到二进制位,BSGS 换到 i⋅P−ji \cdot \sqrt P - j 的两侧分解,扩展 Lucas 换到"质数幂 + 剥离 pp 因子"的坐标系。 写实现时三处最容易错的边界是:

  1. type=2type=2 中 x=0x = 0 必须在消因子之前判掉,且消因子每一轮都要检查 k≡zk \equiv z;
  2. BSGS 的哈希表同值要保留最大的 jj,否则最小解不成立;
  3. type=3type=3 中 e⩾ae \geqslant a(组合数被 pap^a 整除)要提前返回 00,不能去求不存在的逆元。

数据来源说明:素材源目录 new_ROJ/problems/1806/ 内含 data.py 数据生成脚本, 随仓 10 个测试点及其 .out 均由该脚本自造(std.cpp 跑出并做了正向校验), 题面亦属网络重建版本,出题意图可能与官方原题存在偏差。本人在实现时已把 main.cpp / main.py 与随仓 .out 逐点比对(10/10 一致),并另用暴力程序对 type=2type=2(枚举最小 xx)、type=3type=3(Python 大整数 comb 取模)做了小规模对拍。