Strange List
Contest: Codeforces Round 694 (Div. 2)
Difficulty rating: 1100
Tags: brute force, greedy, implementation, math

You have given an array $$$a$$$ of length $$$n$$$ and an integer $$$x$$$ to a brand new robot. What the robot does is the following: it iterates over the elements of the array, let the current element be $$$q$$$. If $$$q$$$ is divisible by $$$x$$$, the robot adds $$$x$$$ copies of the integer $$$\frac{q}{x}$$$ to the end of the array, and moves on to the next element. Note that the newly added elements could be processed by the robot later. Otherwise, if $$$q$$$ is not divisible by $$$x$$$, the robot shuts down.

Please determine the sum of all values of the array at the end of the process.

Input format:
The first input line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$2 \leq x \leq 10^9$$$) — the length of the array and the value which is used by the robot.

The next line contains integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial values in the array.

It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case output one integer — the sum of all elements at the end of the process.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case the array initially consists of a single element $$$[12]$$$, and $$$x=2$$$. After the robot processes the first element, the array becomes $$$[12, 6, 6]$$$. Then the robot processes the second element, and the array becomes $$$[12, 6, 6, 3, 3]$$$. After the robot processes the next element, the array becomes $$$[12, 6, 6, 3, 3, 3, 3]$$$, and then the robot shuts down, since it encounters an element that is not divisible by $$$x = 2$$$. The sum of the elements in the resulting array is equal to $$$36$$$.

In the second test case the array initially contains integers $$$[4, 6, 8, 2]$$$, and $$$x=2$$$. The resulting array in this case looks like $$$ [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1]$$$.

Example input:
2
1 2
12
4 2
4 6 8 2

Example output:
36
44

Editorial:
Solution 1. Let's represent each element $$$a_{i}$$$ as $$$x^{b_{i}} \cdot c_{i}$$$, where $$$b_{i}$$$ is the maximal possible. Let's take minimum over all values $$$b_{i}$$$, and let's assume it's attained at position $$$j$$$. The robot will add each element to the array $$$b_{j}$$$ times (element at position $$$j$$$ will be the first one, which will stop being divisible by $$$x$$$). However, we should not forget about the prefix before position $$$j$$$: each of those number is divisible by a higher power of $$$x$$$, and this prefix will count towards the total sum. The final answer is $$$(b_{j} + 1) \cdot \sum_{i=1}^{n}a_{i} + \sum_{i=1}^{j-1}a_{i}$$$
In this solution we divide each number $$$a_{i}$$$ by $$$x$$$ to generate the array $$$b_{1}, b_{2}, \ldots, b_{n}$$$, and then it takes $$$O(n)$$$ to compute both sums. The final complexity of the solution is $$$O(n \log A)$$$, where $$$A$$$ denotes the maximum possible element of the array.
Solution 2. Let's maintain the list of pairs $$$\{ a_{i}, cnt_{i} \}$$$ — it indicates a range of $$$cnt_{i}$$$ elements equal to $$$a_{i}$$$. Then we can easily implement the operation performed by the robot: if we consider pair $$$\{ a, cnt \}$$$, we either append the array with a pair $$$\{ \frac{a}{x}, cnt \cdot x \}$$$, or terminate the process. The answer to the problem equals to sum of values $$$a_{i} \cdot cnt_{i}$$$.
Each number $$$a_{i}$$$ will be copied to the end of the array at most $$$O(\log A)$$$ times, since each time $$$a_{i}$$$ is divided by $$$x$$$. Since there are $$$n$$$ elements in the array initially, the total complexity of this solution is $$$O(n \log A)$$$.