BZOJ4869【SHOI2017】相逢是问候 <扩展欧拉定理+线段树>

Problem

【SHOI2017】相逢是问候


Description

希望以维护一个长度为 的数组,这个数组的下标为从 的正整数。
一共有 个操作,可以分为两种:

  1. :表示将第 个到第 个数( )中的每一个数 替换为 ,其中 是一个常数
  2. :求第 个到第 个数的和,即

因为这个结果可能会很大,所以你只需要输出结果 的值即可。

Input

第一行有三个整数
接下来一行 个整数,表示a数组的初始值。
接下来 行,每行三个整数,其中第一个整数表示了操作的类型。
如果是 ,表示这是一个修改操作,操作的参数为
如果是 ,表示这是一个询问操作,操作的参数为

Output

对于每个询问操作,输出一行,包括一个整数表示答案 的值。

Sample Input

1
2
3
4
5
6
4 4 7 2
1 2 3 4
0 1 4
1 2 4
0 1 4
1 1 3

Sample Output

1
2
0
3

HINT

, , , ,

Source

黑吉辽沪冀晋六省联考
鸣谢xlk授权本OJ使用权
鸣谢多名网友提供正确数据,已重测!

标签:扩展欧拉定理 线段树

Solution

数论和数据结构结合。

扩展欧拉定理:
由于 最多 次取 后变为定值 ,所以可以暴力修改,类似区间取模的线段树,需要注意每层指数模的是 取多少次 的值。
因为修改时需要计算 和快速幂,总复杂度为 。预处理 可将复杂度缩小为

Code

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
#include <bits/stdc++.h>
#define MAX_N 50000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
x = 0; int c = getchar(), f = 1;
for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, p, c, k;
int a[MAX_N+5]; lnt phi[MAX_N+5];
lnt tr[MAX_N<<2]; int num[MAX_N<<2];
int getphi(int n) {
int ret = n;
for (int i = 2; i*i <= n; i++)
if (n%i == 0) {
ret = ret/i*(i-1);
while (n%i == 0) n /= i;
}
if (n^1) ret = ret/n*(n-1);
return ret;
}
lnt pow(lnt x, lnt k, lnt MOD) {
lnt ret = 1;
for (; k; k >>= 1, x = 1LL*x*x%MOD)
if (k&1) ret = 1LL*x*ret%MOD;
return ret;
}
lnt calc(lnt x, int k) {
for (int i = k; i; i--) {
if (x >= phi[i]) x = x%phi[i]+phi[i];
x = pow(c, x, phi[i-1]), x = x ? x : phi[i-1];
}
return x;
}
void build(int v, int s, int t) {
if (s == t) {tr[v] = a[s]%p; return;}
build(v<<1, s, mid), build(v<<1|1, mid+1, t);
tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
}
void modify(int v, int s, int t, int l, int r) {
if (num[v] >= k) return;
if (s == t) {tr[v] = calc(a[s], ++num[v]); return;}
if (l <= mid) modify(v<<1, s, mid, l, r);
if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r);
tr[v] = (tr[v<<1]+tr[v<<1|1])%p;
num[v] = min(num[v<<1], num[v<<1|1]);
}
lnt query(int v, int s, int t, int l, int r) {
if (s >= l && t <= r) return tr[v]; lnt ret = 0;
if (l <= mid) (ret += query(v<<1, s, mid, l, r)) %= p;
if (r >= mid+1) (ret += query(v<<1|1, mid+1, t, l, r)) %= p;
return ret;
}
void init() {
phi[0] = p;
for (int i = p; i^1; )
phi[++k] = i = getphi(i);
phi[++k] = 1;
}
int main() {
read(n), read(m), read(p), read(c);
for (int i = 1; i <= n; i++) read(a[i]);
init(), build(1, 1, n);
while (m--) {
int opt, l, r; read(opt), read(l), read(r);
if (opt == 0) modify(1, 1, n, l, r);
if (opt == 1) printf("%lld\n", query(1, 1, n, l, r));
}
return 0;
}
------------- Thanks For Reading -------------
0%