Strange List (Codeforces 1471B)
Tags: Greedy, brute force

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: 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: For each test case output one integer — the sum of all elements at the end of the process.

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]$$$.

Sample Inputs:
2
1 2
12
4 2
4 6 8 2

Sample Outputs:
36
44

Solution (Python):
for _ in range(int(input())):
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    index = None
    level = float('inf')
    dic = {}
    for i in range(n):
        m = a[i]
        if dic.get(m, 'False') == True:
            continue
        c = 0
        while True:
            if m == 0 or m % x != 0:
                break
            m = m // x
            c += 1
            if c >= level:
                break
        if c < level:
            level = c
            index = i
        dic[a[i]] = True
    s = sum(a[:index]) * (level + 1) + sum(a[index:]) * level + sum(a)
    print(s)

Solution (Python):
def calc(a, x, d):
    if d.get(a, -1) != -1:
        return d[a]
    else:
        c = 1
        t = a
        while a % x == 0:
            c += 1
            a //= x
        d[t] = c
        return d[t]
for t in range(int(input())):
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    d = {}
    s = 0
    m = 10 ** 9
    index = 0
    for i in range(n):
        temp = calc(a[i], x, d)
        if temp < m:
            m = temp
            index = i
    for i in range(n):
        if i < index:
            s += a[i] * (m + 1)
        else:
            s += a[i] * m
    print(s)

Solution (Python):
def calc(a, x, d):
    if d.get(a, -1) != -1:
        return d
    c = 1
    t = a
    while a % x == 0:
        c += 1
        a //= x
    d[t] = c
    return d
t = int(input())
for _ in range(t):
    (n, x) = map(int, input().split())
    a = list(map(int, input().split()))
    d = {}
    c = 0
    ind = 0
    temp = 0
    m = 10 ** 9
    flag = False
    for i in range(n):
        d = calc(a[i], x, d)
        if d[a[i]] < m:
            m = d[a[i]]
            ind = i
    for i in range(n):
        if i < ind:
            c += a[i] * (m + 1)
        else:
            c += a[i] * m
    print(c)