1. 题目背景与问题描述
这道题目来自洛谷P2480 [SDOI2010]古代猪文,是一道结合数论多个知识点的经典题目。题目给定整数n、g和质数P=999911659,要求计算:
g^(ΣC(n,i) for i|n) mod P
其中C(n,i)表示组合数,i|n表示i是n的约数。这个表达式看起来简单,但实际计算中会遇到几个关键难点:
- 指数部分ΣC(n,i)会非常大,直接计算不现实
- 模数P虽然是质数,但P-1不是质数,导致常规Lucas定理无法直接应用
- 需要处理g=P的特殊情况
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 解题思路与数学原理
2.1 缩小指数规模
首先我们注意到直接计算g^S mod P(其中S=ΣC(n,i))是不可行的,因为S可能非常大。这里我们需要使用扩展欧拉定理:
a^b ≡ a^(b mod φ(m)) (mod m),当a与m互质时
由于P是质数,φ(P)=P-1。因此当g≠P时:
g^S ≡ g^(S mod (P-1)) (mod P)
这样就将指数从巨大的S缩小到了S mod (P-1)。
2.2 计算组合数模P-1
现在问题转化为计算ΣC(n,i) mod (P-1),其中i遍历n的所有约数。注意到P-1=2×3×4679×35617,这是四个不同质数的乘积。这提示我们可以使用中国剩余定理(CRT)来分解问题。
具体步骤:
- 分别计算C(n,i) mod 2, mod 3, mod 4679, mod 35617
- 用CRT将四个结果合并得到C(n,i) mod (P-1)
- 对所有约数i求和得到最终指数
2.3 组合数模小质数计算
对于每个小质数p∈{2,3,4679,35617},我们可以使用Lucas定理来计算C(n,i) mod p。Lucas定理指出:
C(n,i) ≡ Π C(n_k,i_k) (mod p)
其中n_k和i_k是n和i在p进制下的各位数字。
3. 算法实现细节
3.1 预处理阶乘和逆元
为了高效计算组合数模p,我们需要预处理阶乘和逆元:
cpp复制constexpr int FAC[4]={2,3,4679,35617};
int fac[4][N],inv[4][N];
// 预处理阶乘和逆元
rep(k,
