题解 P2480 【[SDOI2010]古代猪文】
Saliеri
·
·
题解
刚学数论3天，经此一全家桶~~深感恶心~~神清气爽，于是决定写这篇题解的同时，权当是我对简单数论的理解~~记忆力堪忧~~。
若有证明或书写错误错误，敬请斧正，蒟蒻将不胜感激。
因为作者是数论菜鸟，一惊一乍请大佬见谅。
$\operatorname{II}\quad \quad$前置芝士
[欧拉定理](https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/891345?fr=aladdin#2)
（$or$ [费马小定理](https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)），[中国剩余定理](https://baike.baidu.com/item/%E5%AD%99%E5%AD%90%E5%AE%9A%E7%90%86?fromtitle=%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86&fromid=11200132)，[卢卡斯定理](https://baike.baidu.com/item/lucas/4326261)。
证明：下转$\operatorname{V}$区。
$\operatorname{III}\quad \quad$题解
___
$\operatorname{Tips}$:如果有看不懂的定理或步骤，请移步证明区或评论区。
___
题目极其冗长，去其糟粕~~几乎全是糟粕~~之后：
- 远古时期猪文文字总个数为 $n$。
- 那个朝代流传的猪文文字恰好为远古时期的 $\frac{1}{k}$，其中 $k$ 是 $n$ 的一个正约数（可以是 $1\ $或 $n$）。（枚举约数）
- 然而从 $n$ 个文字中保留下 $\frac{n}{k}$ 个的情况也是相当多的。(即组合数)
- 所有可能的 $k$ 的所有情况数加起来为 $p$ 的话，那么他研究古代文字的代价将会是 $g^p$。
可以得到题目真正需要求的柿子（枚举$n/d$与$d$是一样的，也为了好看）：
$$g^{\sum \limits_{d|n} \operatorname{C}_n^{d}} \operatorname{mod} 9999111659$$
$\operatorname{Case\ 1}:$当 $\quad \color{red}{999911659|g}\quad$时,$\operatorname{Ans}=0$;(一定要判！)
$\operatorname{Case\ 2}:
由欧拉定理,或费马小定理（999911659为质数）:
=g^{\sum \limits_{d|n} \operatorname{C}_n^{d} \operatorname{mod}999911658} \operatorname{mod} 9999111659
即求：
\sum \limits_{d|n} \operatorname{C}_n^{d} \operatorname{mod}999911658
然后————好像没辙了。
题目所要求的组合数的n,m的数量级高达10^9,只有卢卡斯定理可担此重任，但是……
我们怀着忐忑的心情将$999911658$分解质因数：
$$999911658 = 2 \times3\times4679\times35617$$
只有一次项！
这说明我们可以对四个质因子分别求解。
问题又来了，如何合并答案？
这次很简单：因为四个模数两两互质~~毕竟都是质数~~，所以中国剩余定理即可。
于是，我们来理一下思路：
- 对四个模数分别求出$\sum \limits_{d|n} \operatorname{C}_n^{d} \operatorname{mod} p_i$的值分别为$ans_i$（其中组合数使用卢卡斯定理）。
- 用中国剩余定理求出线性同余方程组：
$\begin{cases}S \equiv ans_1(\operatorname{mod}p_1) \\S \equiv ans_2(\operatorname{mod}p_2) \\S \equiv ans_3(\operatorname{mod}p_3)\\
S \equiv ans_4(\operatorname{mod}p_4)\end{cases}
的在\left[0,999911658\right] 中的解。
- 快速幂求出g^S \operatorname{mod} 999911659
然后这题就做完了（好像也不是很难）。
```cpp
#include <cstdio>
#define int long long//记得开longlong <== Mod*mod > intmax!
const int maxd = 36000,Mod = 999911659;
int N,g;
inline int ksm(int a,int x,int p) {//快速幂不解释
int ans = 1,base = a;
while(x) {
if(x & 1)ans = ans*base%p;
base = base*base%p,x >>= 1;
}
return ans;
}
struct Lucas {
int mod,pre[maxd],inv[maxd];//O(1)组合数准备：阶乘与阶乘逆元（逆元求法见注释）
inline void getpreinv() {
pre[0] = inv[0] = 1;
for(int i=1; i<=mod-1; ++i)pre[i] = pre[i-1]*i%mod;
inv[mod-1] = ksm(pre[mod-1],mod-2,mod);//单个使用快速幂
for(int i=mod-2; i; --i)inv[i] = inv[i+1]*(i+1)%mod;
}
inline int C(int m,int n) {return m>n?0:pre[n]*inv[m]%mod*inv[n-m]%mod;}//C(m,n) = n!/m!(n-m)! = n!*inv[m!]*inv[(n-m)!]
inline int lucas(int m,int n) {
if(m==0)return 1;
return C(m%mod,n%mod)*lucas(m/mod,n/mod)%mod;
}//Lucas定理
} S[5];
int mod[] = {0,2,3,4679,35617},sum[5],M[5],Mp[5];
signed main() {
scanf("%lld %lld",&N,&g);
if(g == Mod){printf("0");return 0;}
for(int i=1; i<=4; ++i)S[i].mod = mod[i],S[i].getpreinv();//组合数预处理
for(int i=1;i*i<=N;++i)//枚举约数统计答案
if(N%i == 0)
for(int j=1;j<=4;++j){
sum[j] = (sum[j]+S[j].lucas(i,N))%S[j].mod;
if(i*i!=N)sum[j] = (sum[j]+S[j].lucas(N/i,N))%S[j].mod;//如果i==n/i则只算一次！
}
for(int i=1;i<=4;++i)M[i] = (Mod-1)/S[i].mod,Mp[i] = ksm(M[i],S[i].mod-2,S[i].mod);
long long S = 0;
for(int i=1;i<=4;++i)S += (long long)(M[i]*Mp[i]*sum[i]);
S = (S%(Mod-1)+Mod-1)%(Mod-1);//中国剩余定理求法见证明区
printf("%lld",ksm(g,S,Mod));
return 0;
}
```
注释：
- 阶乘逆元求法：
> - 快速幂得到$((mod-1)!)^{-1}
___
$\operatorname{i}\quad $ 欧拉定理
注：费马小定理是欧拉定理的特殊情况，所以只证欧拉。
**定义**：（为了更好懂，省去了一点严谨性，大佬轻喷）
- 同余类：所有除$m$余$i$的整数构成模$m$的一个同余类，记为$\overline{i}$.
- 完全剩余系（并不重要）：所有模m的同余类的集合。（即$\left\{\overline{0},\overline{1}\cdots\overline{m-1}\right\}$）
- **简化剩余系**:在$\overline0\cdots \overline {m-1}$这$m$个同余类中，**余数与$m$互质**的同余类构成模$m$的简化剩余系。由定义易知，模$m$的简化剩余系中共有$\varphi(m)$个同余类。（注：$0$不与$m$互质）。
**证明**：（运算都在模$m$意义下进行）
- 引理 ： 当$\operatorname{gcd}(a,m) = 1$时，对于任意$b_i \neq b_j $,有$a\cdot b_i \neq a\cdot b_j
- 证明：
显然因为\operatorname{gcd}(a,m) = 1，所以在模m意义下一定存在a的逆元，两边同乘即证。
设模m的简化剩余系为\{\overline{b_1}\cdots\overline{b_{\varphi(m)}}\},由引理知，各个a\cdot b_i两两不同，所以\{\overline{a\cdot b_1}\cdots\overline{a\cdot b_{\varphi(m)}}\}也构成模m的简化剩余系。
\Rightarrow b_1\cdot b_2 \cdots b_{\varphi(m)} \equiv (a\cdot b_1)\cdot (a\cdot b_2) \cdots (a\cdot b_{\varphi(m)}) \equiv a^{\varphi(m)}\cdot b_1\cdot b_2 \cdots b_{\varphi(m)}
两边同乘 b_1\cdot b_2 \cdots b_{\varphi(m)}的逆元(\because \forall b_i,\operatorname{gcd}(b_i,m)=1，即存在逆元)
\Rightarrow a^{\varphi(m)} \equiv 1
证毕。
注： 代入m\in prime则有a^{m}\equiv a,即费马小定理。
其实就是个构造……
我们有一个同余方程组，其中满足模数两两互质：
\begin{cases}S \equiv ans_1(\operatorname{mod}p_1) \
\vdots\
S \equiv ans_n(\operatorname{mod}p_n)\end{cases}
构造方案 ：
- 我们令$M = \prod m_i,m'_i = M/m_i$。
- 构造$t_i$满足$m'_i\cdot t_i \equiv 1(\operatorname{mod}m_i)
- 则同余方程组的一个特解为\sum m'_it_ians_i,在模M意义下的解即为最小正整数解。
构造正确性证明：
实现 ：
- 其中t_i即为m'_i的乘法逆元，具体求法exgcd或快速幂均可。
太神了，虽然证明很初等，但是我不会……
[挂链接跑路](https://zhuanlan.zhihu.com/p/116698264)(讲的真的好)
___
$\operatorname{VI}\quad $ 结束
虽然本文章极其初等~~甚至有些ZZ~~，数论菜鸟恳请大家斧正，这会对我后来的学习起到很大帮助，谢谢！
求过