Description

给定 $n,g$，求

$$g^{\displaystyle\sum_{d|n}\binom {n} {d}} \pmod {999911659}\\ \text{999911659 is a prime number} $$

Solution

容易发现指数非常大， 所以考虑使用 ex 欧拉定理缩小指数：

$$a^b \pmod m = a^{b\mod \varphi(m)+\varphi(m)}\pmod m(\text{s.t.}\;b\ge \varphi(m)) $$

注意到当 $m$ 为质数时， $\varphi(m)=m-1$，故我们要求

$$\sum_{d|n}\binom{n}{d}\pmod {999911658}$$

这个时候我们的问题转化成了求组合数模非质数。

考虑将 $999911658$ 进行质因数分解，可以得到 $999911658=4679\times3\times2\times35617$

这个时候我们只需要对这四个质数分别求出解，最后用 CRT 求出最小的非负整数解即可。

来复习一下 CRT：

求同余方程组

$$x\equiv a_i\pmod {m_i}$$

的解，其中 $m_i$ 是两两互质的整数。

记 $M=\displaystyle\prod_{i}m_i,M_i=\dfrac {M} {m_i},t_i=M_i^{-1}\pmod {m_i}$

则有解 $x=\displaystyle\sum_{i} M_it_ia_i$，此时，对于任意 $m_i$，都有 $x\equiv a_i\pmod{m_i}$

求组合数对质数取模，我们可以使用 Lucas 定理，即：

$$\binom{n}{m}\pmod p=\binom{n\bmod p}{m\bmod p}\times\binom{\dfrac n p}{\dfrac m p}\pmod p $$