P15566 [COCI 2025/2026 #5] Weight / Težina

The full score for this problem is $70$.

In front of the strongman Karlo at the gym, there is an array $a$ of length $n$, where $a_i$ represents the weight of the $i$-th item. He can also use $k$ different “weight types”, numbered $1,2,\dots,k$. For each weight type from $1$ to $k$, Karlo considers every item in the array in order and follows the process below: 1. Compute the result of dividing the item’s weight by the current weight type (discard the fractional part), and record this integer. 2. Multiply this integer by “the item’s weight $+2$”. If the resulting integer is greater than $10^8$, replace it with $10^8$. 3. Add up the integers obtained for all items to get the “strength value” of this weight type. Karlo wants to know the sum of the strength values of all weight types. Please help him solve this problem.

The first line contains two natural numbers $n,k$ ($1 \le n,k \le 10^5$), representing the number of items and the number of weight types. The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ($1 \le a_i \le 10^5$).

Output one integer on a single line, representing the required total sum.

#### Sample Explanation Explanation for Sample #2: In this sample, there is only weight type $1$: - $3 \to 3 \cdot (3+2)=15$ - $4 \to 4 \cdot (4+2)=24$ The total sum is $39$. #### Subtasks | Subtask | Score | Constraints | | :----: | :--: | :--: | | $1$ | $17$ | $k \le 300$ | | $2$ | $19$ | The number of distinct values in array $a$ is at most $300$ | | $3$ | $34$ | No additional constraints | Translated by ChatGPT 5