前言
之前听朋友说cry出题很抽象，一直没留意，直到今天做了这个题，迷迷糊糊看题解发现一头雾水，发现出题人是cry……
（不过感觉题目还是挺不错的，只是题解我看不懂）
题意
有一个程序:
1
2
3
4
5
6
7
| function f(k, a, l, r):
ans := 0
for i from l to r (inclusive):
while k is divisible by a[i]:
k := k/a[i]
ans := ans + k
return ans
|
对于q个询问，求出f(k,a,l,r)的值
题解
题目理解
首先读给出的程序代码（应该是伪代码），了解一下大致流程，大概是说对于数组a，枚举从l到r的每个i，用ai更新k的值，并将ans的值加k。具体来说，当ai为k的因数时，k会不断的自除以ai，直到ai不再为k的因数。
比较重要的应该就是更新k的部分。显然只有ai为k的因数时k才会被更新，所以当ai不能整除k时，ans在原来值基础上直接+k即可。
实现
一个简单的思路是我们对于每次查询，将i从l到r枚举，不断暴力的更新k，但这个做法显然复杂度过高。
注意到q的范围为5e4，区间[l, r]长度最大为1e5，显然我们不能枚举到区间中的所有值。
那么我们需要注意哪些值呢？
注意到只有k的因数可以更新k，我们可以预处理出k的所有因数，并预处理出这些因数f所有出现的位置，存储在数组fac[f]中。显然对于k的某个因数f, fac[f]为一个单调递增的数组，那么我们可以通过二分查找第一个不小于l的索引，并判断该索引存在且不大于r，我们就可以用这个索引的元素更新到k。
但还有一点需要注意的就是k更新的顺序是由数组顺序决定的，而不是因数大小决定的。所以我们可以用一个小根堆维护k所有因数的合法索引，并用数组中的相应元素更新k。
对于这些因数索引以外的位置，记prel为上次的索引，top为当前取出的索引，有(top - prel - 1)长度的一段元素没有更新k，他们对ans的贡献为这个长度乘以prel时更新得到的k。
最后用最后的索引和r之间的一段元素用相同方式更新ans即可。
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
| #include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
int n, qq;
int a[N];
vector<int> facs[N];
vector fac(N, vector<int>());
void solve() {
cin >> n >> qq;
for(int i = 1; i <= n; ++i) {
cin >> a[i];
fac[a[i]].push_back(i);
}
int k, l, r;
for(int i = 1; i <= qq; ++i) {
cin >> k >> l >> r;
priority_queue<int, vector<int>, greater<>> q;
for(int f : facs[k]) {
auto pos = lower_bound(fac[f].begin(), fac[f].end(), l);
if(pos != fac[f].end() and *pos <= r) q.push(*pos);
}
int ans = 0, prel = l - 1;
while(k > 1 && q.size()) {
int top = q.top(); q.pop();
ans += (top - prel - 1) * k;
while(k % a[top] == 0) k /= a[top];
ans += k;
prel = top;
}
ans += k * (r - prel);
cout << ans << '\n';
}
for(int i = 1; i <= n; ++i) fac[a[i]].clear();
}
main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
for(int i = 1; i < N; ++i) {
for(int j = i; j < N; j += i) {
facs[j].push_back(i);
}
}
int t; cin >> t;
while(t--) {
solve();
}
return 0;
}
|
一些细节
西安站前的一场vp（好像就是2024年的西安邀请赛）去学到了调和级数算时间复杂度，可以注意到这里的预处理正好时间复杂度是O(NlogN)的。每个k的因数数量大概是sqrtk级别的，所以solve函数主循环的复杂度大概为$O(q\sqrt{k}\log{n})$(做题之前压根猜不到的复杂度)
