跳转至

BZOJ4869 相逢是问候

题面

维护长为 N(N\leq 50000) 的数组，支持两个操作：

  1. 0\ \ l\ \ r 将l至r中的数a_i变为c^{a_i}，其中c为一个一开始给定的常数。
  2. 1\ \ l\ \ r　查询l到r中所有数的和。

操作数为M(M\leq 50000)。

输出全部 \mod p,p为一个一开始就给定的常数(p\leq 10^8)。

题解

又是一道和扩展欧拉定理有关的线段树题。

根据扩展欧拉定理:

a^b\equiv\begin{cases} a^{b\bmod\varphi(p)},\,&\gcd(a,\,p)=1\\ a^b,&\gcd(a,\,p)\ne1,\,b<\varphi(p)\\ a^{b\bmod\varphi(p)+\varphi(p)},&\gcd(a,\,p)\ne1,\,b\ge\varphi(p) \end{cases} \pmod p

那么如果设d=c^x

那么c^{c^x}=c^d,当d>\varphi(p)时：

\Large c^d=c^{d\%\varphi(p)+\varphi(p)}=c^{c^x\%\varphi(p)+\varphi(p)}
\huge =c^{c^{x\%\varphi(\varphi(p))+\varphi(\varphi(p))}+\varphi(p)}

经过自己手动将剩下的\varphi(p)一个个提出来之后发现会有很多\varphi套在一起。

然后注意到p变到\varphi(p),\varphi(\varphi(p))，只要\log p次就会变成1。

当\varphi^k(p)=1时c^{x\%\varphi}=0，于是此时就不需要继续修改这个点了。

于是建一颗线段树，线段树每个节点维护两个值，一个是这个区间中数之和sum，另一个是区间中修改次数最少的数的个数mn。

当节点的mn的值\geq p变成1所需步数时不用修改当前节点，否则递归下去暴力修改。

但是这样的复杂度为n\log^2n\cdot\log p,无法通过此题，但是使用Sengxian的方法可以将c^x\% \varphi^k(p)优化到O(1).

Sengxian的方法

具体做法是预处理 \mathrm{pow_1}(n) 表示 c^n\bmod p 的值，处理到 65536；再预处理 \mathrm{pow_2}(n) 表示 c^n 平方 16 次 \mathrm{mod}\;p 的值，同样处理到 65536，则 c^x\bmod p 可以通过分两段查表的方式快速算出：

pow1[b & 65535] * pow2[b >> 16] % mod

由于只有 O(\log n) 个模数，对每个模数都预处理，那么复杂度为：O(65536 \cdot 16\log n)。

程序

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define MAX_N 100007
#define ls (x << 1)
#define rs (x << 1 | 1)
#define __x % __y (__x - __x / __y * __y)
#define reg register
typedef long long ll;

int N, M, tot;
ll MOD, C, sum[MAX_N * 4], mn[MAX_N * 4], a[MAX_N];
ll pow1[50][1 << 16], pow2[50][1 << 16], cnt[50];
std::map<ll, int> phi, nums;

template <typename T> inline void read (reg T& x) {
    x = 0;
    reg char c = getchar();
    while (c < '0' || '9' < c) c = getchar();
    while ('0' <= c && c <= '9') x = x * 10 + c - '0', c = getchar();
}

inline ll quick_pow (reg ll x, reg ll p, reg ll mod) {
    if (C == 1) return mod <= 1 ? 0 : 1;
    reg ll ans = 1, tmp = 0;
    while (p) {
        if (p & 1) {
            ans = ans * x;
        }
        if (ans >= mod) ans = ans % mod, tmp = 1;
        p >>= 1;
        x = x * x;
        if (x >= mod) x = x % mod;
    }
    return ans + tmp * mod;
}

inline ll quick_quick_pow (reg ll x, reg ll mod) {
    reg int idx = nums[mod];
    if (x < cnt[idx]) return pow1[idx][x];
    return pow1[idx][x & 65535] * pow2[idx][x >> 16] % mod + mod;
}

inline ll calc (reg ll x, reg int cnt, reg ll mod) {
    if (mod == 0) return 0;
    if (C == 1) return C % mod;
    if (cnt == 0) return x < mod ? x : x % mod + mod;
    return quick_quick_pow(calc(x, cnt - 1, phi[mod]), mod);
}

inline ll calc (reg ll x) {
    reg ll ans = x, m = sqrt(x) + 1;
    for (reg ll i = 2;i <= m; ++i) 
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) ans = ans / x * (x - 1);
    return ans;
}

inline void init () {
    reg ll p = MOD, tmp, x;
    while (p > 1) {
        nums[p] = ++tot;
        tmp = calc(p);
        phi[p] = tmp;
        p = tmp;
    }
    nums[1] = ++tot;
    phi[1] = 0;
    p = MOD;
    for (reg int i = 1;i <= tot; ++i) {
        pow1[i][0] = 1;
        for (reg int j = 1, endd = (1 << 16); j < endd; ++j)
            pow1[i][j] = pow1[i][j - 1] * C % p;
        for (reg int j = 0, endd = (1 << 16); j < endd; ++j) {
            pow2[i][j] = pow1[i][j];
            for (reg int k = 0;k < 16; ++k)
                pow2[i][j] = pow2[i][j] * pow2[i][j] % p;
        }
        tmp = 0;
        x = 1;
        while (C != 1 && x < p) {
            x *= C, ++tmp;
        }
        cnt[i] = tmp;
        p = phi[p];
    }
}

inline ll min (ll a, ll b) {return a < b ? a : b;}

inline void update (reg int x) {
    sum[x] = sum[ls] + sum[rs];
    if (sum[x] > MOD) sum[x] = sum[x] % MOD;
    mn[x] = min(mn[ls], mn[rs]);
}

void build (reg int x, reg int l, reg int r) {
    if (l == r) {
        read(a[l]);
        sum[x] = a[l];
        return;
    }
    reg int mid = l + r >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    update(x);
}

void modify (reg int x, reg int l, reg int r, reg int ql, reg int qr) {
    if (l > qr || r < ql) return;
    if (mn[x] >= tot) return;
    if (l == r) {
        sum[x] = calc(a[l], ++mn[x], MOD);
        return;
    }
    reg int mid = l + r >> 1;
    if (ql <= mid) modify(ls, l, mid, ql, qr);
    if (mid < qr) modify(rs, mid + 1, r, ql, qr);
    update(x);
}

ll query (reg int x, reg int l, reg int r, reg int ql, reg int qr) {
    if (l > qr || r < ql) return 0;
    if (ql <= l && r <= qr) return sum[x];
    reg int mid = l + r >> 1;
    reg ll ans = 0;
    if (ql <= mid) ans = query(ls, l, mid, ql, qr) % MOD;
    if (mid < qr) ans = (ans + query(rs, mid + 1, r, ql, qr) % MOD) % MOD;
    return ans % MOD;
}

int main () {
    read(N), read(M);
    read(MOD), read(C);
    init();
    build(1, 1, N);
    reg int op, l, r;
    while (M--) {
        read(op);
        read(l);
        read(r);
        if (op == 0) { //modify
            modify(1, 1, N, l, r);
        } else { //query
            printf("%lld\n", query(1, 1, N, l, r) % MOD);
        }
    }
    return 0;
}