We Were Both Children (Codeforces 1850F)
Tags: Math, number theory

Mihai and Slavic were looking at a group of $$$n$$$ frogs, numbered from $$$1$$$ to $$$n$$$, all initially located at point $$$0$$$. Frog $$$i$$$ has a hop length of $$$a_i$$$. Each second, frog $$$i$$$ hops $$$a_i$$$ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.However, the children can't go far away from their home so they can only place a trap in the first $$$n$$$ points (that is, in a point with a coordinate between $$$1$$$ and $$$n$$$) and the children can't place a trap in point $$$0$$$ since they are scared of frogs.Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?

Input: The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.The second line of each test case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the lengths of the hops of the corresponding frogs.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.

Note: In the first test case, the frogs will hop as follows:   Frog 1: $$$0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$$$  Frog 2: $$$0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$$$  Frog 3: $$$0 \to 3 \to 6 \to 9 \to 12 \to \cdots$$$  Frog 4: $$$0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$$$  Frog 5: $$$0 \to 5 \to 10 \to 15 \to 20 \to \cdots$$$  Therefore, if Slavic and Mihai put a trap at coordinate $$$4$$$, they can catch three frogs: frogs 1, 2, and 4. It can be proven that they can't catch any more frogs.In the second test case, Slavic and Mihai can put a trap at coordinate $$$2$$$ and catch all three frogs instantly.

Sample Inputs:
7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10

Sample Outputs:
3
3
3
5
0
4
4

Solution (Python):
def main():
    t = int(input())
    results = []
    for i in range(t):
        n = int(input())
        aa = list(map(int, input().split()))
        results.append(solution(n, aa))
    print('\n'.join(map(str, results)))

def solution(n, aa):
    ca = [0] * (n + 1)
    for a in aa:
        if a <= n:
            ca[a] += 1
    cc = [0] * (n + 1)
    for a in range(n + 1):
        c = ca[a]
        if c > 0:
            for j in range(a, n + 1, a):
                cc[j] += c
    return max(cc)
main()

Solution (Python):
def zlicz(n, a):
    maxi = max(a)
    Z = [0] * (n + 1)
    m = len(Z)
    for i in range(n):
        if a[i] < m:
            Z[a[i]] += 1
    return Z

def sito(n, Z):
    S = [0] * n
    for i in range(n):
        if Z[i]:
            tmp = Z[i]
            for x in range(i, n, i):
                S[x] += tmp
    return S

def solve(n, a):
    Z = zlicz(n, a)
    n = len(Z)
    S = sito(n, Z)
    return max(S)

def main():
    t = int(input())
    for tests in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        print(solve(n, a))
main()

Solution (Python):
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log, log2, pi, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from heapq import *
from collections import deque
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceildiv = lambda x, d: -(x // -d)
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 998244353

def main():
    n = stdint()
    ar = sorted(map(int, stdstr().strip().split()))
    x = []
    y = []
    c2 = [0] * (n + 1)
    last = 0
    for i in ar:
        if i == last:
            y[-1] += 1
        else:
            x.append(i)
            y.append(1)
        last = i
    for (i, v) in zip(x, y):
        for j in range(0, n + 1, i):
            c2[j] += v
    stdpr(max(c2[1:]))
    stdpr('\n')
for i in range(stdint()):
    main()