C. Removing Smallest Multiples

题目链接（Codeforces Round #822 Div. 2 C）

题目描述

给定集合 S = {1, 2, ..., n}，以及它的一个子集 T（用长度为 n 的二进制字符串表示，第 i 位为 '1' 表示 i ∈ T，为 '0' 表示 i ∉ T）。

你可以执行任意次以下操作：

• 选择一个正整数 k（1 ≤ k ≤ n），满足 S 中存在 k 的倍数；
• 删除 S 中 最小的 k 的倍数；
• 本次操作代价为 k。

求将 S 变为 T（即删除所有不在 T 中的元素，保留 T 中的元素）所需的最小总代价。

数据范围：

• 1 ≤ t ≤ 10000
• 1 ≤ n ≤ 10^6
• 所有测试用例的 n 之和不超过 10^6

示例

输入：

6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

输出：

0
11
4
4
17
60

解释（第二个测试用例）：

n = 7，S = {1,2,3,4,5,6,7}，T = {1,2,4,7}（字符串 1101001 表示 1、2、4、7 位为 1）。

操作：

• 选 k = 3，删除 3（代价 3）；
• 选 k = 3，删除 6（代价 3）；
• 选 k = 5，删除 5（代价 5）。

总代价 3 + 3 + 5 = 11，且为最小。

核心思路

对于每个需要删除的数字 x（即 s[x-1] == '0'），我们希望用一个尽可能小的 k 来删除它，使得 x 是 k 的倍数，且对于所有小于 x 的 k 的倍数 y，y 也必须是需要删除的（即 s[y-1] == '0'）。否则，删除最小 k 倍数时会先删到 y，如果 y 需要保留，则不能使用这个 k。

因此，对每个 x，我们找满足以下条件的最小 k：

• x % k == 0；
• 对于所有 j < x 且 j % k == 0，都有 s[j-1] == '0'。

贪心策略：从小到大枚举 k，然后枚举 k 的倍数 m = k, 2k, 3k, ...：

• 如果 s[m-1] == '1'，说明这个倍数需要保留，不能删除。因此对于当前 k，所有更大的倍数都不能用 k 删除（因为会先遇到这个保留的倍数），直接 break；
• 如果 s[m-1] == '0'，且 m 之前还没有被更小的 k 删除过，则用当前 k 删除 m 是最优的（因为 k 是从小到大枚举的，第一次遇到 m 时的 k 就是最小可用 k）。记录 m 已被删除，答案累加 k。

如果 m 已经被更小的 k 处理过，则跳过，继续看下一个倍数。

为什么总复杂度可接受：

枚举 k 的倍数的总次数为：

$$\sum_{k=1}^{n} \frac{n}{k} = O(n \log n)$$

对于所有测试用例的 n 之和不超过 10^6，O(n \log n) 约为 2 × 10^7 次操作，在 2 秒内可以完成。

方法：从小到大枚举 k + 枚举倍数

思路及解法

1. 读入 n 和二进制字符串 s。
2. 创建一个布尔数组 removed（或 used），长度为 n + 1，初始全为 False，表示该数字是否已经被删除。
3. 初始化答案 ans = 0。
4. 对于 k 从 1 到 n：
   • 如果 s[k-1] == '1'，说明 k 本身需要保留，那么 k 不能用于删除任何数（因为第一个倍数 k 就无法删除），直接跳过当前 k。
   • 否则，枚举 m = k, 2k, 3k, ... 直到 m > n：
     • 如果 s[m-1] == '1'，说明这个倍数需要保留，break（后面的倍数都不能用 k 删除）。
     • 如果 s[m-1] == '0' 且 not removed[m]：
       • 标记 removed[m] = True；
       • 答案 ans += k。
     • 如果 s[m-1] == '0' 但 removed[m] 已为 True，则直接继续下一个倍数（这个数已被更小的 k 删除，不影响当前 k 继续处理后面的倍数）。
5. 输出 ans。

代码（C++）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n;
        string s;
        cin >> n >> s;

        vector<bool> removed(n + 1, false);
        long long ans = 0;

        for (int k = 1; k <= n; ++k) {
            if (s[k - 1] == '1') continue; 
            for (int m = k; m <= n; m += k) {
                if (s[m - 1] == '1') break;  
                if (!removed[m]) {
                    removed[m] = true;
                    ans += k;
                }
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

代码（Python）

t = int(input())
for _ in range(t):
	n = int(input())
	s = input().strip()
	removed = [False] * (n + 1)
	ans = 0
	for k in range(1, n + 1):
		if s[k - 1] == '1':
			continue
		for m in range(k, n + 1, k):
			if s[m - 1] == '1':
				break
			if not removed[m]:
				removed[m] = True
				ans += k
	print(ans)

复杂度分析

• 时间复杂度：$O(n \log n)$ 每个测试用例，所有测试用例的 $n$ 之和不超过 $10^6$，总时间约为 $O(\sum n \log n)$，可以接受。
• 空间复杂度：$O(n)$，需要 removed 数组和字符串。

关键细节

1. 为什么 k 本身为 '1' 时可以跳过

如果 s[k-1] == '1'，说明数字 k 需要保留。而 k 是 k 的最小倍数，操作要求删除最小的 k 的倍数，但 k 不能被删除，因此无法用 k 删除任何数。直接跳过即可。

2. 为什么遇到 s[m-1] == '1' 就 break

对于固定的 k，它的倍数依次为 k, 2k, 3k, ...。操作总是删除当前最小的 k 的倍数。如果遇到了一个需要保留的倍数 m，那么当 m 是当前最小的 k 的倍数时，无法删除它，操作被阻塞，因此更大的倍数也永远无法用 k 删除。所以直接 break。

3. 为什么第一次遇到 m 时的 k 就是最优

外层 k 从小到大枚举。对于任意需要删除的 m，所有能删除它的 k 都是 m 的约数。我们按 k 从小到大尝试，第一次能够成功删除 m 的 k 就是所有可行 k 中最小的，因此代价最小。

4. 已被删除的 m 为什么要继续遍历

如果 m 已经被更小的 k 删除，对于当前 k 来说，m 已经从 S 中移除。当前 k 仍然可以继续处理 m 后面的倍数（因为当前最小的 k 的倍数已经变成了下一个未被删除的倍数）。所以不能 break，直接跳过 m 继续下一个倍数。

5. 答案可能很大

最坏情况下 n = 10^6，如果全部删除，代价可能达到 $\sum_{k=1}^{n} k \approx 5 \times 10^{11}$，因此需要用 long long（C++）或 Python 自动大整数。

总结

• 核心贪心：对每个需要删除的数，找最小的可行 k。
• 实现方式：从小到大枚举 k，再枚举它的倍数，遇到保留的数就停止。
• 复杂度：调和级数 $O(n \log n)$，总规模 $10^6$ 可以轻松通过。
• 通用套路：「删除倍数」类问题 → 枚举约数/倍数 + 贪心。

相关题目

• Codeforces 1734C. Removing Smallest Multiples（本题）
• 数论中调和级数枚举的常见应用：埃拉托斯特尼筛法、约数枚举等。