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

花淇淋 · 2019-02-04 16:00:38 · 题解

Solution

• 建议先做这题
• 根据扩展欧拉定理 a^b\% p ≡ a^{b \%\phi(p)+\phi(p)}\% p,b≥\phi(p) a^b\% p ≡ a^{b \%\phi(p)}\% p,b<\phi(p)
• 这题核心代码如下

  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]
• 可知 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

#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;
}