AcWing 1108. 读书
原题链接
简单
作者:
wzc1995
,
2019-10-23 11:15:52
,
所有人可见
,
阅读 846
算法
(预处理) $O(n \log n + Q)$
- 对于每个 1 到
n
的数,我们枚举它的倍数,然后判断这个倍数是否是残破的,预处理这个数有多少个不是残破的页。
- 对于每个询问,直接输出预处理好的答案即可。
时间复杂度
- 预处理的复杂度为 $\sum_{i=1}^{n} \frac{n}{i} = O(n \log n)$,每个询问直接给出答案。
- 故总时间复杂度为 $O(n \log n + Q)$。
空间复杂度
C++ 代码
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100010;
#define LL long long
int p[N];
bool t[N];
int main() {
int T, n, m, Q;
scanf("%d", &T);
for (int kase = 1; kase <= T; kase++) {
scanf("%d%d%d", &n, &m, &Q);
for (int i = 1; i <= n; i++) {
p[i] = n / i;
t[i] = false;
}
for (int i = 1, x; i <= m; i++) {
scanf("%d", &x);
t[x] = true;
}
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i)
if (t[j])
p[i]--;
LL ans = 0;
while (Q--) {
int x;
scanf("%d", &x);
ans += p[x];
}
printf("Case #%d: %lld\n", kase, ans);
}
return 0;
}