题目描述
给你一个数组$a_i$，$D(x)$为$x$的约数个数
两种操作：
1.将$[l,r]$的$a_i$替换为$D(a_i)$
2.输出$\sum^r_{i=l}a_i$
输入样例
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
输出样例
30
13
4
22
Solution
这道题和上帝造题七分钟2有点相似，只不过是把区间开放方成了区间改约数个数。
标记是块内是否每个数都小于等于2。
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
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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 3010002
#define MX 1000100
#define ll long long
using namespace std;
int b[MAXN], n, sq, m;
ll s[MAXN], a[MAXN];
bool v[MAXN];
bool chk[MX];
int p[MX], d[MX], tot, num[MX];
inline int max(int a, int b) {
if (a > b) return a;
else return b;
}
inline int min(int a, int b) {
if (a < b) return a;
else return b;
}
void getd() {
chk[1] = 0;
d[1] = 1;
for (int i = 2; i <= MX; i++) {
if (!chk[i]) {
p[++tot] = i;
d[i] = 2;
num[i] = 1;
}
for (int j = 1; j <= tot && i * p[j] <= MX; j++) {
chk[i * p[j]] = 1;
if (!(i % p[j])) {
num[i * p[j]] = num[i] + 1;
d[i * p[j]] = d[i] / (num[i] + 1) * (num[i * p[j]] + 1);
break;
}
else {
d[i * p[j]] = d[i] * d[p[j]];
num[i * p[j]] = 1;
}
}
}
}
inline void quarysqrt(int x) {
if (v[x]) return;
v[x] = 1;
a[x] = 0;
for (int i = (x - 1) * sq + 1; i <= x * sq; i++) {
s[i] = d[s[i]];
a[x] += s[i];
if (s[i] > 2) v[x] = 0;
}
}
inline void add(int x, int y) {
if (v[b[x]] == 0) {
for (int i = x; i <= min(b[x] * sq, y); i++) {
a[b[x]] -= s[i];
s[i] = d[s[i]];
a[b[x]] += s[i];
}
v[b[x]] = 1;
for (int i = (b[x] - 1) * sq + 1; i <= b[x] * sq; i++) {
if (s[i] > 2) {
v[b[x]] = 0;
break;
}
}
}
if (b[x] != b[y] && v[b[y]] == 0) {
for (int i = (b[y] - 1) * sq + 1; i <= y; i++) {
a[b[y]] -= s[i];
s[i] = d[s[i]];
a[b[y]] += s[i];
}
v[b[y]] = 1;
for (int i = (b[y] - 1) * sq + 1; i <= b[y] * sq; i++) {
if (s[i] > 2) {
v[b[y]] = 0;
break;
}
}
}
for (int i = b[x] + 1; i <= b[y] - 1; i++) {
quarysqrt(i);
}
}
ll getsum(int x , int y) {
ll ans = 0;
for (int i = x; i <= min(b[x] * sq , y); i++) {
ans += s[i];
}
if (b[x] != b[y]) {
for (int i = (b[y] - 1) * sq + 1; i <= y; i++) {
ans += s[i];
}
}
for (int i = b[x] + 1; i < b[y]; i++) {
ans += a[i];
}
return ans;
}
int main() {
memset(v, 0, sizeof (v));
scanf("%d%d", &n, &m);
getd();
sq = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &s[i]);
}
for (int i = 1; i <= n; i++) {
b[i] = (i - 1) / sq + 1;
a[b[i]] += s[i];
}
for (int i = 1; i <= m; i++) {
int x, y, c;
scanf("%d%d%d", &c, &x, &y);
if (x > y) {
swap(x, y);
}
if (c == 1) {
add(x, y);
}
else printf("%lld\n", getsum(x, y));
}
return 0;
}
|
