Removing Smallest Multiples (Codeforces 1734C)
Tags: Greedy, math

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.

Input: 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$$$. 

Output: For each test case, output one non-negative integer — the minimum possible total cost of operations such that $$$S$$$ would be transformed into $$$T$$$.

Note: 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:   Choose $$$k=3$$$, then delete $$$3$$$ from $$$S$$$.  Choose $$$k=3$$$, then delete $$$6$$$ from $$$S$$$.  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$$$.

Sample Inputs:
6
6
111111
7
1101001
4
0000
4
0010
8
10010101
15
110011100101100

Sample Outputs:
0
11
4
4
17
60

Solution (Python):
import sys, threading, bisect, heapq, math, copy
from heapq import heappush, heappop
from functools import cmp_to_key as ctk, lru_cache
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
show = lambda arr: print(' '.join(map(str, arr)))
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    for _wzl_ in range(int(input())):
        (n,) = read()
        s = input()
        arr = alloc(False, n + 1)
        res = 0
        for i in range(1, n + 1):
            if s[i - 1] == '1':
                continue
            for j in range(i, n + 1, i):
                if s[j - 1] == '1':
                    break
                if not arr[j]:
                    arr[j] = True
                    res += i
        print(res)
main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    s = [1] + list(input().rstrip())
    ans0 = 0
    for i in range(1, n + 1):
        j = i
        while j <= n and s[j] ^ 49:
            if not s[j] & 1:
                ans0 += i
                s[j] = 1
            j += i
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from calendar import c
from cmath import inf
from math import ceil, gcd, sqrt, log2
import os
import sys
from io import BytesIO, IOBase
from collections import Counter, defaultdict, deque
from heapq import heappush, heappop
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def lcm(a, b):
    return a * b // gcd(a, b)
for _ in range(int(input())):
    n = int(input())
    T = input()
    summ = 0
    A = [-1] * n
    ans = 0
    for k in range(1, n + 1):
        fac = 1
        while k * fac <= n and T[k * fac - 1] == '0':
            if A[k * fac - 1] == -1:
                A[k * fac - 1] = k
                ans += k
            fac += 1
    print(ans)