Codeforces Round 694 (Div. 2) |
---|
Закончено |
На Новый Год Дима получил целых два подарка: массив $$$a$$$ длины $$$n$$$ и число $$$x$$$. Оба подарка ему очень понравились, и он сразу же начал экспериментировать с ними. Для этого он отдал их своему новому роботу.
Робот обрабатывает элементы массива по очереди. Пусть текущий рассматриваемый элемент равен $$$q$$$. Если $$$q$$$ кратно $$$x$$$, то робот дописывает в конец массива $$$x$$$ копий числа $$$\frac{q}{x}$$$, а после этого переходит к следующему элементу массива. Обратите внимание, что добавленные элементы могут быть рассмотрены роботом в будущем. Если же $$$q$$$ не делится на $$$x$$$, то робот немедленно прекращает работу.
Определите, чему будет равна сумма элементов массива после того, как робот закончит работу.
Первая строка содержит одно число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$2 \leq x \leq 10^9$$$) — количество элементов массива и число, на которое робот делит элементы массива.
Следующая строка содержит целые числа $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — изначальные элементы массива.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите одно число — сумму элементов после окончания процесса.
2 1 2 12 4 2 4 6 8 2
36 44
В первом наборе входных данных массив изначально состоит лишь из одного числа: $$$[12]$$$, а $$$x = 2$$$. После рассмотрения первого элемента массив превратится в $$$[12, 6, 6]$$$. После обработки второго элемента массив будет содержать элементы $$$[12, 6, 6, 3, 3]$$$. После обработки третьего элемента массив будет состоять из чисел $$$[12, 6, 6, 3, 3, 3, 3]$$$, а после этого робот рассмотрим следующий элемент, который не делится на $$$x=2$$$, и завершит работу. Сумма чисел в итоговом массиве равна $$$36$$$.
Во втором наборе входных данных массив изначально состоит из чисел $$$[4, 6, 8, 2]$$$, а $$$x=2$$$. Итоговый массив выглядит как $$$ [4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1]$$$.
Название |
---|