A15444 | Removing Smallest Multiples
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
You are given a set $S$ , which contains the first $n$ positive integers: $1, 2, \ldots, n$ .
You can perform the following operation on $S$ any number of times (possibly zero):
- Choose a positive integer $k$ where $1 \le k \le n$ , such that there exists a multiple of $k$ in $S$ . Then, delete the smallest multiple of $k$ from $S$ . This operation requires a cost of $k$ .
You are given a set $T$ , which is a subset of $S$ . Find the minimum possible total cost of operations such that $S$ would be transformed into $T$ . We can show that such a transformation is always possible.
You can perform the following operation on $S$ any number of times (possibly zero):
- Choose a positive integer $k$ where $1 \le k \le n$ , such that there exists a multiple of $k$ in $S$ . Then, delete the smallest multiple of $k$ from $S$ . This operation requires a cost of $k$ .
You are given a set $T$ , which is a subset of $S$ . Find the minimum possible total cost of operations such that $S$ would be transformed into $T$ . We can show that such a transformation is always possible.
输入格式
The first line of the input contains a single integer $t$ ( $1 \le t \le 10\,000$ ) — the number of test cases. The description of the test cases follows.
The first line contains a single positive integer $n$ ( $1 \le n \le 10^6$ ).
The second line of each test case contains a binary string of length $n$ , describing the set $T$ . The $i$ -th character of the string is '1' if and only if $i$ is an element of $T$ , and '0' otherwise.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ .
The first line contains a single positive integer $n$ ( $1 \le n \le 10^6$ ).
The second line of each test case contains a binary string of length $n$ , describing the set $T$ . The $i$ -th character of the string is '1' if and only if $i$ is an element of $T$ , and '0' otherwise.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ .
输出格式
For each test case, output one non-negative integer — the minimum possible total cost of operations such that $S$ would be transformed into $T$ .
输入输出样例
输入 #1
6 6 111111 7 1101001 4 0000 4 0010 8 10010101 15 110011100101100
输出 #1
0 11 4 4 17 60
In the first test case, we shall not perform any operations as $S$ is already equal to $T$ , which is the set $\{1, 2, 3, 4, 5, 6\}$ .
In the second test case, initially, $S = \{1, 2, 3, 4, 5, 6, 7\}$ , and $T = \{1, 2, 4, 7\}$ . We shall perform the following operations:
1. Choose $k=3$ , then delete $3$ from $S$ .
2. Choose $k=3$ , then delete $6$ from $S$ .
3. Choose $k=5$ , then delete $5$ from $S$ .
The total cost is $3+3+5 = 11$ . It can be shown that this is the smallest cost possible.
In the third test case, initially, $S = \{1, 2, 3, 4\}$ and $T = \{\}$ (empty set). We shall perform $4$ operations of $k=1$ to delete $1$ , $2$ , $3$ , and $4$ .
In the fourth test case, initially, $S = \{1, 2, 3, 4\}$ and $T = \{3\}$ . We shall perform two operations with $k=1$ to delete $1$ and $2$ , then perform one operation with $k=2$ to delete $4$ .
In the second test case, initially, $S = \{1, 2, 3, 4, 5, 6, 7\}$ , and $T = \{1, 2, 4, 7\}$ . We shall perform the following operations:
1. Choose $k=3$ , then delete $3$ from $S$ .
2. Choose $k=3$ , then delete $6$ from $S$ .
3. Choose $k=5$ , then delete $5$ from $S$ .
The total cost is $3+3+5 = 11$ . It can be shown that this is the smallest cost possible.
In the third test case, initially, $S = \{1, 2, 3, 4\}$ and $T = \{\}$ (empty set). We shall perform $4$ operations of $k=1$ to delete $1$ , $2$ , $3$ , and $4$ .
In the fourth test case, initially, $S = \{1, 2, 3, 4\}$ and $T = \{3\}$ . We shall perform two operations with $k=1$ to delete $1$ and $2$ , then perform one operation with $k=2$ to delete $4$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted