洛谷5071 - [Ynoi2015]此时此刻的光辉

根据小学我们就学过的一个简单公式,如果 $x = \prod p_i ^ { a_i } $ 那么 $x$ 因子个数为 $\prod a_i + 1$ 。因此我们需要维护查询的区间内每一个质数的和。

考虑把原来的数分解,这一步我们只需要预处理出小于 $ \sqrt { \max {a_i} }$ 的质数即可。然后对于每个数 $ a_i $ 依次判断小于 $ a_i $ 的质数。复杂度 $ O( \frac {n \sqrt{\max{a_i}}} {\log n} )$ ,实际情况下表现非常优越。或者采用 Pollard-Rho 算法优化为 $ n \times \sum { a_i^{ 1 / 4 } }$ ,但实现会较为复杂而且没有必要。

接下来考虑分解出的质数如何处理,如果直接放在一起去莫队的话复杂度是 $ O(n \sqrt n \log n) $ ,如果常数不优秀的话会 TLE 。我们考虑一个优化方式,对于大小在前 $\sqrt n$ 个的范围内的质数,预处理出个数,前缀和统计,不参与莫队,其余分解出的质数参与莫队,可以证明,每一个数需要参与莫队的数的个数是 $O(1)$ 级别的。这样的话复杂度降为 $n \sqrt n$ ,事实上我们可以把范围由 $\sqrt n$ 调整为 $100$ ~ $200$ 左右以获得一个较小的常数,跑到目前效率 rank 1。

代码:

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
// =================================
// author: memset0
// date: 2018.12.09 20:57:04
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
namespace ringo {
typedef long long ll;

template < class T >
inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}

template < class T >
inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}

template < class T >
inline void print(T x, char c) {
print(x), putchar(c);
}

const int N = 1e5 + 10, M = sqrt(1e9) + 10, L = 150, p = 19260817;
int n, m, ul, ur, ql, qr, now = 1, pos, max, sqn, limit;
int a[N], b[N], c[N], ans[N], bln[N], pri[N << 1], lazy[N], cnt[N << 1];
bool vis[M];
std::map < int, int > map;
int inv[N * 20], sum[N][L + 1];

struct pair {
int first, second;
pair () {}
pair (int _first, int _second) { first = _first, second = _second; }
};
std::vector < pair > v[N];

struct query {
int l, r, i;
inline bool operator < (const query &other) const {
if (bln[l] == bln[other.l]) return bln[l] & 1 ? r > other.r : r < other.r;
return l < other.l;
}
} q[N];

inline void push_back(int k, int first, int second) {
if (first <= L) sum[k][first] += second;
else v[k].push_back(pair(first, second));
}

inline void pre(int a, int k) {
int cnt = 0;
for (int i = 1; pri[i] * pri[i] <= a && i <= pri[0]; i++)
if (!(a % pri[i])) {
cnt = 0;
while (!(a % pri[i])) ++cnt, a /= pri[i];
push_back(k, i, cnt);
}
if (a != 1) {
auto it = map.find(a);
if (it == map.end()) map[a] = ++pos, pri[pos] = a, a = pos;
else a = it->second;
push_back(k, a, 1);
}
}

inline void add(int x) {
for (auto u : v[x]) {
now = (ll)now * inv[cnt[u.first] % p] % p;
cnt[u.first] += u.second;
now = (ll)now * cnt[u.first] % p;
}
}

inline void del(int x) {
for (auto u : v[x]) {
now = (ll)now * inv[cnt[u.first] % p] % p;
cnt[u.first] -= u.second;
now = (ll)now * cnt[u.first] % p;
}
}

void main() {
read(n), read(m), sqn = n / sqrt(m * 2.0 / 3);
for (int i = 1; i <= n; i++) {
read(a[i]), b[i] = a[i];
max = std::max(max, a[i]);
bln[i] = (i - 1) / sqn;
}
std::sort(b + 1, b + n + 1);
int tn = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; i++)
c[i] = std::lower_bound(b + 1, b + tn + 1, a[i]) - b;
limit = sqrt(max);
for (int i = 2; i <= limit; i++) {
if (!vis[i]) pri[++pri[0]] = i, map[i] = pri[0];
for (int j = 1; j <= pri[0] && i * pri[j] <= limit; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
pos = pri[0], max = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= L; j++) sum[i][j] = sum[i - 1][j];
pre(a[i], i);
for (auto u : v[i]) cnt[u.first] += u.second;
}
for (int i = 1; i <= pos; i++) max = std::max(max, cnt[i]);
inv[0] = inv[1] = 1, limit = max + 1;
for (int i = 2; i <= std::min(limit, p - 1); i++) inv[i] = (ll)(p - p / i) * inv[p % i] % p;
for (int i = 1; i <= pos; i++) cnt[i] = 1;
for (int i = 1; i <= m; i++) read(q[i].l), read(q[i].r), q[i].i = i;
std::sort(q + 1, q + m + 1);
ul = 1, ur = 0;
for (int i = 1; i <= m; i++) {
ql = q[i].l, qr = q[i].r;
while (ul > ql) add(--ul);
while (ur < qr) add(++ur);
while (ul < ql) del(ul++);
while (ur > qr) del(ur--);
ans[q[i].i] = now;
for (int j = 1; j <= L; j++) {
ans[q[i].i] = (ll)ans[q[i].i] * (sum[qr][j] - sum[ql - 1][j] + 1) % p;
}
for (int i = 1; i <= m; i++) print(ans[i], '\n');
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×