题解：P16741 [GKS 2019 #G] Book Reading

Qi_Aolang · 2026-06-04 19:04:08 · 题解

题目大意

有一本共 n 页的书，撕掉了 m 页，有 q 名读者，第 i 名读者只读页码是 R_i 的倍数且没被撕掉的页面。

问每个读者阅读的页数之和。

代码讲解

我们可以定义一个数组 h，用来存储当前页是否被撕掉：

    for (int i = 1, p; i <= m; i ++) {
        cin >> p;
        h[p] = 0; //0代表被撕掉
    }

再定义一个数组 s，用来存储当前下标的倍数有几页被撕掉了，可以得到如下代码：

    for (int i = 1; i <= n; i ++) {
        for (int j = i; j <= n; j += i) { //判断倍数
            if (!h[j]) s[i] ++; //如果当前页被撕掉，贡献加一
        }
    }

最后查询 q 次，每次让答案加上 r 的小于 n 的未被撕掉的倍数个数：

    for (int i = 1, r; i <= q; i ++) {
        cin >> r;
        ans += (n / r) - s[r]; //n / r 为向下取整，正好是 r 的小于 n 的倍数个数
    }

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, n, m, q, s[100007];
bool h[100007];
int32_t main ()
{
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    cin >> T;
    for (int case1 = 1; case1 <= T; case1 ++) {
        cin >> n >> m >> q;
        memset(h, 1, sizeof h);
        memset(s, 0, sizeof s);
        for (int i = 1, p; i <= m; i ++) {
            cin >> p;
            h[p] = 0;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = i; j <= n; j += i) {
                if (!h[j]) s[i] ++;
            }
        }
        int ans = 0;
        for (int i = 1, r; i <= q; i ++) {
            cin >> r;
            ans += (n / r) - s[r];
        }
        cout << "Case #" << case1 << ": " << ans << "\n";
    }
    return 0;
}

写题解不易，点个赞再走吧！