1850F.md (2493B)
1 Source: https://codeforces.com/problemset/problem/1850/F 2 3 F. We Were Both Children 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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. 24 25 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. 26 27 Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap? 28 29 Input 30 31 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. 32 33 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. 34 35 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. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap. 42 43 Example 44 45 Input 46 47 ``` 48 7 49 50 5 51 52 1 2 3 4 5 53 54 3 55 56 2 2 2 57 58 6 59 60 3 1 3 4 9 10 61 62 9 63 64 1 3 2 4 2 3 7 8 5 65 66 1 67 68 10 69 70 8 71 72 7 11 6 8 12 4 4 8 73 74 10 75 76 9 11 9 12 1 7 2 5 8 10 77 ``` 78 79 Output 80 81 ``` 82 3 83 3 84 3 85 5 86 0 87 4 88 4 89 ``` 90 91 Note 92 93 In the first test case, the frogs will hop as follows: 94 95 * Frog 1: $0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$ 96 * Frog 2: $0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$ 97 * Frog 3: $0 \to 3 \to 6 \to 9 \to 12 \to \cdots$ 98 * Frog 4: $0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$ 99 * Frog 5: $0 \to 5 \to 10 \to 15 \to 20 \to \cdots$ 100 101 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. 102 103 In the second test case, Slavic and Mihai can put a trap at coordinate $2$ and catch all three frogs instantly.