[六省联考2017]相逢是问候
经历
经过费力地琢磨题解、几天的酝酿和一个下午的调试，我终于写完了这一题。个人认为这个题还是有积累套路的必要的。
题目链接
https://www.luogu.com.cn/problem/P3747
注：尽量在洛谷提交，因为 LOJ 时限较宽松，而考试不可能。
题解
第一步
得出结论：\(c^{c^{c^{...^x}}}(共w个c)\mod p\) 在 \(w>2\log_2 p\) 后就不再变化。（这是一个上限，也就是说可能还没有到 \(2\log_2 p\) 就不再变化了。）
为什么呢？分类讨论，当 \(p\) 是一个奇质数的时候，\(\varphi(p)=p-1\) 是一个偶数，当 \(p\) 是一个合数时，\(\varphi(p)\le \frac{p}{2}\) 因为 \([1,p]\) 范围内的偶数一定都不和 \(p\) 互质。因此极限情况是“质数→合数→质数→合数……”，其中质数到合数数量级不变，而合数→质数就除以了2，即证。
下面对这个结论进行应用。
\[根据欧拉定理，当c^{c^{c^{...^x}}}(共w-1个c)\ge \varphi(p)时，\\ c^{c^{c^{...^x}}}(共w个c)\mod p=c^{(c^{c^{c^{...^x}}}(共w-1个c)\bmod \varphi(p)+\varphi (p))} \]因此我们转为计算 \(c^{c^{c^{...^x}}}(共w-1个c)\bmod \varphi(p)\)。
\[根据欧拉定理，当c^{c^{c^{...^x}}}(共w-2个c)\ge \varphi(\varphi(p))时，\\ c^{c^{c^{...^x}}}(共w-1个c)\mod p=c^{(c^{c^{c^{...^x}}}(共w-2个c)\bmod \varphi(\varphi(p))+\varphi (\varphi(p)))} \]于是我们可以一直迭代下去，直到——
- \(c^{c^{...^x}}<\varphi(p)\)，则直接计算 \(^①\)
- 或 \(模数=1\)，则答案必为 0
- 或上面两条都没有到但是已经迭代完了（现在只需要返回 \(x\)）
因此我们可以写出下面的 calc 函数：
int calc(int x,int p){
if(p==1)return 0;
if(x==w+1||w-x+1<=5&&h[id][w-x+1]p了，而2已经是最小的c了
int t=calc(x+1,g[x]);
return qp(c,t+g[x],p);
}
上面注解的①就是指，由于 \(MAXN·2log_2p·2log_2p\) 只会是几e7可以支持（其中前一个 \(2log_2p\) 表示每个数至多修改这么多次就不会变化，后一个表示每次修改暴力调用calc函数给 \(ai\) 需要迭代的次数），因此可以这么做。
不过等等，上面的复杂度分析好像掉了一些什么，就是我们的快速幂是 \(O(\log p)\) 的，因此我们不得不 \(O(1)\) 地计算快速幂。观察到快速幂的特殊性——底数始终是 \(c\)，而模数就是 \(p,\varphi(p),\varphi(\varphi(p)),...\) 这一串，数量是不超过 \(2\log p\) 的，因此：
- 考虑对每一个模数 \(m\)，预处理出 \(ksm_{0,m,j}(j=0,1,...,\sqrt{2\times 10^8})\) 表示 \(\text{qp}(c,j,m)\)，以及 \(ksm_{1,m,j}(j=0,1,...,\sqrt{2\times 10^8})\) 表示 \(\text{qp}(c,\sqrt{2\times 10^8}\cdot j,m)\)，这样一来对于每一个 \(l\)，我们都可以将 \(l\) 写成 \(l/\sqrt{2\times 10^8}+l\mod \sqrt{2\times 10^8}\)(/表示整除)，从而算得 \(\text{qp}(c,l,p_0)=ksm_{0,l/\sqrt{2\times 10^8},p_0}\cdot ksm_{1,l\mod \sqrt{2\times 10^8},p_0}\mod p_0\)
第二步
下面就比较简单了。考虑处理询问中的命令。
一个简单的思路是分块。
对于修改命令，我们考虑维护一个链表，如果一个数已经达到饱和（指已经被修改 \(2log_2p\) 次）就在链表中删除它表示以后再不需要访问它。每次从 \([l,r]\) 中第一个在链表中的位置开始暴力跳链表直到超过 \(r\)，并暴力更新 \(a_i\)，同时对 \(a_i\) 所在的整块的 \(sum\) 加上变化量。
对于询问命令，按照模板的分块求和即可。
可悲的是
LOJ 洛谷
这个算法不仅跑得很慢，而且会 TLE。
所以其实还可以用线段树维护，常数会小很多。
对于修改命令，利用线段树不带下穿标记地寻找并暴力调用calc修改 \([l,r]\) 中的每一个非饱和元素，同时利用线段树维护区间和。
对于查询命令，按照模板的线段树求和即可。
可喜的是
LOJ 洛谷
但可惜用了太多时间在以为可以压线过的卡常上。
提交记录中已经能看到代码，故不再展示。
积累
需要积累的是：
- 遇到 \(k^{k^{一大串}}\) 时的基本思路
- 欧拉定理的灵活应用和递推功能
- 这类修改到一定程度就不会变化的序列的快速维护方式，相似问题