题解 P3747 【[六省联考2017]相逢是问候】

# Solution - 建议先做[这题](https://www.luogu.org/problemnew/show/P4139) - 根据扩展欧拉定理 $$a^b\% p ≡ a^{b \%\phi(p)+\phi(p)}\% p,b≥\phi(p)$$ $$a^b\% p ≡ a^{b \%\phi(p)}\% p,b<\phi(p)$$ - [这题](https://www.luogu.org/problemnew/show/P4139)核心代码如下 ```cpp inline int solve(int p) // 递归处理模数为p的答案 { if (p == 1) return 0; return ksm(2, solve(phi[p]) + phi[p], p); // ksm(x,y) = x ^ y } ``` - 发现每次递归都会将 $p$ 变为 $\phi(p)$ - 当 $p$ 是偶数时， $p$ 变 $\phi(p)$ 至少除以 $2$；当 $p$ 是奇数时，根据 $\phi(p)$ 的计算公式 ($q[i]$ 为 $p$ 的所有质因子，且互不相同)$$p*\Pi_{i=1}^k(q[i]-1)\div q[i]$$ - $q[i]-1$必有偶数，那么$\phi(p)$是偶数 - **可知 $p$ 会在 $O(\log p)$ 内次变为 $1$，结束递归** **** - 而上题中，对扩展欧拉定理的应用为：$$2^{2^{2^{2^{...}}}}\% p ≡ 2^{2^{2^{2^{...}}} \%\phi(p)+\phi(p)}$$ - 假设 $2$ 的个数有限，等式左边有 $x$ 个 $2$， 那么等式右边的指数，也就是递归处理的部分，有 $x-1$ 个 $2$ - 也就是说，每次递归减少了一个 $2$ - **那么减少 $O(\log p)$ 个 $2$ 后必定结束递归，即当 $2$ 的个数超过 $\log p$ 时，答案全部一样** - 回到本题，可以得出一个数的修改次数上限为 $O(\log p)$ - 那么维护线段树，如果整个区间修改次数都到上限了，就 $return$ - 易得一共会碰到叶子节点 $O (n \log p)$ 次 **** - ~~为了方（偷）便（懒）~~ ，记 $b[i][j]$ 为 $c^{c^{c^{...^{a_{i}}}}}$ (共 $j$ 个 $c$，**注意没有取模**），记 $f(i,j,p)$ 为 $c^{c^{c^{...^{a_{i}}}}} \%p$ (共 $j$ 个 $c$)，那么有递推式$$f(i,j,p)=c^{f(i,j-1,\phi(p))+(b[i][j-1]<\phi(p)?0:\phi(p))}$$ - **预处理几个值在 $1e8$ 内的 $b[i][j]$** 就好了，显然 $j$ 都比较小，$j$ 稍大一点就是天文数字了，肯定比 $\phi(p)$ 大，当然，**注意特判 $c=1$ 和 $j$ 较大的情况** - **$p$ 有 $1e8$，不能用数组把所有的 $\phi(x),x≤p$ 都存下来**，发现用到的 $x$ 只有 $p,\phi(p),\phi(\phi(p)),...,1$，考虑预处理出所有这样的 $x$，并存下它们的 $\phi$，记这些 $x$ 分别为 $d[m..1]$（即 $d[k-1] = \phi(d[k])$），那么上式改写为$$f(i,j,k)=c^{f(i,j-1,k-1)+(b[i][j-1]<d[k-1]?0:d[k-1])}$$ - 注意递归边界：$j=0$ 或 $k=1$ - 由于用到快速幂，上式时间复杂度 $O (\log^2p)$ - 发现 $f(i,j,m)$ 不能直接由 $f(i,j-1,m)$ 得来，也就是说，每次到叶子节点都要重新计算，那么总复杂度 $O (n \log n \log^2p)$，~~直接爆炸~~，考虑优化掉快速幂 **** - **对于这$m$个模数**，分别预处理 $c1[i]$ 为 $c^{i*20000}$，$c2[i]$ 为 $c^i$，那么 $$c^y=c1[y/20000]*c2[y\%20000]$$ - 然后就可以 $O(1)$ 快速幂了 - 总时间复杂度 $O(n (\log n \log p + \log^2p))$ # Code ```cpp #include <bits/stdc++.h> using namespace std; #define ll long long #define p2 p << 1 #define p3 p << 1 | 1 template <class t> inline void read(t & res) { char ch; while (ch = getchar(), !isdigit(ch)); res = ch ^ 48; while (ch = getchar(), isdigit(ch)) res = res * 10 + (ch ^ 48); } const int e = 5e4 + 5, o = 5e4 + 5, bl = 2e4, z = 105; int a[e], cnt[o * 4], c1[z][20005], c2[z][20005], n, m, c, mod, phi[e]; int num[e], d[e], c4, c3[e], b[e][20], sum[o * 4]; inline void upt(int &x, int y) { x = y; if (x >= mod) x -= mod; } inline int solve(int x) { int s = sqrt(x), res = x, i; for (i = 2; i <= s; i++) if (x % i == 0) { while (x % i == 0) x /= i; res /= i; res *= i - 1; } if (x > 1) { res /= x; res *= x - 1; } return res; } inline void init() { d[d[0] = 1] = mod; for (;;) { d[0]++; d[d[0]] = solve(d[d[0] - 1]); if (d[d[0]] == 1) break; } reverse(d + 1, d + d[0] + 1); int i, j; ll y = 1; c3[0] = 1; for (i = 1; i < bl; i++) { if (y <= 1e8) { y = y * c; c3[i] = y; if (y <= 1e8) c4 = i; } else break; } for (i = 1; i <= d[0]; i++) { c1[i][0] = c2[i][0] = 1; for (j = 1; j < bl; j++) c2[i][j] = (ll)c2[i][j - 1] * c % d[i]; c1[i][1] = (ll)c2[i][bl - 1] * c % d[i]; for (j = 2; j < bl; j++) c1[i][j] = (ll)c1[i][j - 1] * c1[i][1] % d[i]; } for (i = 1; i <= n; i++) { b[i][0] = a[i]; for (j = 1; j <= 6; j++) { int x = b[i][j - 1], p1 = x / bl, p0 = x % bl; if (c3[p0] > 1e8 || p1 || p0 > c4) break; b[i][j] = c3[p0]; num[i] = j; } } } inline int ksm(int y, int id) { return (ll)c1[id][y / bl] * c2[id][y % bl] % d[id]; } inline int f(int i, int j, int mod) { if (mod == 1) return 0; if (j == 0) return a[i] % d[mod]; if (c == 1 || (c != 1 && j - 1 <= num[i] && b[i][j - 1] < d[mod - 1])) return ksm(f(i, j - 1, mod - 1), mod); else return ksm(f(i, j - 1, mod - 1) + d[mod - 1], mod); } inline void collect(int p) { cnt[p] = min(cnt[p2], cnt[p3]); upt(sum[p], sum[p2] + sum[p3]); } inline void build(int l, int r, int p) { if (l == r) { sum[p] = a[l]; return; } int mid = l + r >> 1; build(l, mid, p2); build(mid + 1, r, p3); collect(p); } inline void update(int l, int r, int s, int t, int p) { if (cnt[p] > d[0]) return; if (l == r) { cnt[p]++; sum[p] = f(l, cnt[p], d[0]); return; } int mid = l + r >> 1; if (s <= mid) update(l, mid, s, t, p2); if (t > mid) update(mid + 1, r, s, t, p3); collect(p); } inline int query(int l, int r, int s, int t, int p) { if (l == s && r == t) return sum[p]; int mid = l + r >> 1, res = 0; if (t <= mid) res = query(l, mid, s, t, p2); else if (s > mid) res = query(mid + 1, r, s, t, p3); else upt(res, query(l, mid, s, mid, p2) + query(mid + 1, r, mid + 1, t, p3)); return res; } int main() { read(n); read(m); read(mod); read(c); int i, opt, l, r; for (i = 1; i <= n; ++i) read(a[i]); init(); build(1, n, 1); while (m--) { read(opt); read(l); read(r); if (!opt) update(1, n, l, r, 1); else printf("%d\n", query(1, n, l, r, 1)); } return 0; } ```