Luogu P2480 [SDOI2010] 古代猪文 题解

前言

标题传送门 Luogu P2480 [SDOI2010] 古代猪文。
非常好数学题。假如你学过扩展 Lucas ，大概会以为比力简单。
题意

给定 \(n\) ，对于全部 \(k \mid n\) ，统计从 \(n\) 个中选出 \(k\) 个的方案数之和，记为 \(p\) 。盘算 \(g^p\bmod 999911659\) 。
包管 \(n,g\le 10^9\) 。
思绪

起首是个人都能一眼瞧出答案应该是：

\[ans=g^{\sum_{i \mid n}\binom{n}{i}} \bmod m\]
我们思量怎么求这个式子。
起首不难发现指数太大了。轻易发现 \(999911659\) 是一个质数，以是我们利用欧拉降幂，轻易得到下面的式子：

\[a n s \equiv g^{\sum_{i \mid n}\binom{n}{i} \bmod \varphi(m)}\pmod {m}\]
然后我们发现 \(\binom{n}{i}\) 也是一个非常大的数。用 \(O(n)\) 的预处理处罚肯定是不大概的；\(\varphi(m)=m-1=999911658\) 又不是质数，无法利用卢卡斯定理。怎么办呢？
下面是最关键的一步。注意到 \(999911658=2\times 3\times 4679\times 35617\) 。这四个质因数的指数都是 \(1\) 。这是个很有用的性子。我们令 \(a = \binom{n}{i}\) ，设 \(a \equiv x \pmod{\varphi(m)}\) ，只要求 \(x\) 即可。记以上四个质因数为 \(m_1\sim m_4\) ，由中国剩余定理，这相称于我们只要求解如下方程组：

\[\left\{ \begin{array}{l l l} x \equiv a _ {1} & \pmod{m_1} \\ x \equiv a _ {2} & \pmod{m_2} \\ x \equiv a _ {3} & \pmod{m_3} \\ x \equiv a _ {4} & \pmod{m_4} \end{array} \right.\]
由于 \(m_1\sim m_4\) 都是质数，以是 \(a_1\sim a_4\) 可以用卢卡斯定理求得。然后利用 CRT 归并求解这个方程组就行了。
注意特判当 \(g=m=999911659\) 的情况。
代码

[code]#include#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)#define int long long#define MIKU 0using namespace std;// 999911658 = 2 * 3 * 4679 * 35617const int mod = 999911659, pm = mod-1;int n, g, pw;int a[5], m[5] = {0, 2, 3, 4679, 35617};int fac[5][36000], finv[5][36000];int qpow(int a, int n, int mod, int res = 1) {        while(n) {                if(n & 1) res = res * a % mod;                a = a * a % mod;                n >>= 1;        }        return res;}void init() {        for(int i=1; i