LOJ2142 [SHOI2017]相逢是问候

神秘扩展欧拉定理 + 均摊线段树。

题意：维护一个长度为 $n$ 的序列 $a$ ，修改是对 $[l, r]$ 将 $a_{i}$ 变为 $c^{a_{i}}$ ，或者询问 $\sum_{i = l}^{r} a_{i}$ ，输出 $mod p$ 的答案就可。 $n, c$ 开始给定， $n, q \times 5 \times 10^{4}$ ， $p \leq 10^{8}$ 。

显然 $a_{i}$ 的值仅和 $a_{i}$ 的初始值以及修改操作覆盖的次数有关。看到如此庞大的数，考虑扩展欧拉定理： $a^{n} \equiv a^{n mod φ (p) + φ (p)} (\mod p)$ ，这时需要保证 $n \geq φ (p)$ 。

如果不操作，那么和 $a_{i} mod p$ 的值有关；如果操作一次，和 $a_{i} mod φ (p)$ 有关；如果操作两次，即 $c^{a_{i}} mod φ (p)$ 有关，即 $a_{i} mod φ (φ (p))$ 有关……这样下去，当 $φ (φ \dots (p)) = 1$ 的时候，这个答案和 $a_{i}$ 和操作次数都没有关了，它变成了一个定值（和操作次数无关是因为再操作相当于修改 $a_{i}$ ，没有什么用了）。

这样我们只需要维护前几次操作。大概是多少次呢？

结论：该深度为 $O (\log p)$ 级别。

证明：对于偶数来说， $φ (p) \leq \frac{p}{2}$ ；对于奇数来说， $2 | φ (p)$ ，可以由 $φ (p)$ 的定义式得到。

这样我们就只需要暴力计算前 $O (\log n)$ 项即可。计算由于是暴力计算，而且不能利用前面的信息，只能依次按照原式计算。时间复杂度 $O (n \log^{3} n + q \log n)$ ，不太能过。

注意到我们的一个 $\log$ 是来自于快速幂的，但是容易发现底数只有一种，模数只有 $O (\log p)$ 种，于是光速幂预处理，可以做到 $O (n \log^{2} n + q \log n + \sqrt{q} \log p)$ ，可以通过。

注意扩展欧拉定理只能在 $n \geq φ (p)$ 时才能使用，所以需要判断指数是否 $\geq φ (p)$ 。

struct LPow {
	static const int B = 32768;
	int sk[B], bk[B], Mod;
	LPow() : Mod(1) {}
	
	void init(int _Mod)
	{
		Mod = _Mod;
		sk[0] = bk[0] = 1;
		for (int i = 1; i < B; ++ i) sk[i] = (LL) sk[i - 1] * c % Mod;
		bk[1] = (LL) sk[B - 1] * c % Mod;
		for (int i = 2; i < B; ++ i) bk[i] = (LL) bk[i - 1] * bk[1] % Mod;
	}
	
	int lpow(int x) { return bk[x >> 15] * (LL) sk[x & (B - 1)] % Mod; }
} lp[70];

int phi(int n)
{
	int res = n;
	for (int i = 2; i <= n / i; ++ i)
		if (n % i == 0) {
			res /= i, res *= (i - 1);
			while (n % i == 0) n /= i;
		}
	if (n ^ 1) res /= n, res *= (n - 1);
	return res;
}

struct Node {
	int l, r, cnt, sum;
} tr[N << 2];

void pushup(int x)
{
	adj(tr[x].sum  = tr[x << 1].sum + tr[x << 1 | 1].sum - Mod);
	tr[x].cnt = std::min(tr[x << 1].cnt, tr[x << 1 | 1].cnt);
}

void build(int x, int l, int r)
{
	tr[x] = {l, r, 0, a[l]};
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
	pushup(x);
}

void modify(int x, int l, int r)
{
	if (tr[x].cnt > lim || tr[x].l > r || tr[x].r < l) return;
	if (tr[x].l == tr[x].r) {
		tr[x].cnt ++;
		int cur = a[tr[x].l];
		bool flag = false;
		for (int i = tr[x].cnt; i; -- i)
		{
			int tmp = cur;
			LL res = 1;
			while (tmp -- && !flag) {
				res *= c;
				if (res >= lp[i].Mod) {
					flag = true;
					break;
				}
			}
			cur = lp[i].lpow(cur);
			if (flag || lp[i].Mod == 1) cur += lp[i].Mod;
		}
		tr[x].sum = cur % Mod;
		return;
	}
	modify(x << 1, l, r), modify(x << 1 | 1, l, r);
	pushup(x);
}

int query(int x, int l, int r)
{
	if (tr[x].l > r || tr[x].r < l) return 0;
	if (tr[x].l >= l && tr[x].r <= r) return tr[x].sum;
	int tmp;
	return adj(tmp = query(x << 1, l, r) + query(x << 1 | 1, l, r) - Mod);
}