Рейд-Босс
(Время: 2 сек. Память: 32 Мб Сложность: 42%)
В одной компьютерной RPG-игре проходит ивент, на который собралось N игроков. Каждый из них имеет одного персонажа с уровнем Li, являющимся целым числом.
Для того, чтобы начать бой с рейд-боссом, уровень каждого игрока должен являться точной D-степенью. Число A является точной D-степенью, если A=XD для некоторого целого X.
К счастью, во внутриигровом магазине продаются зелья изменения уровней. Зелье объёма S стоит S монет, где S – любое целое положительное число. Игрок может применить зелье на персонажа и, по своему усмотрению, уровень станет либо в S раз больше, либо в S раз меньше. При этом второй случай допустим только если уровень персонажа на момент принятия зелья делится на S.
Зелье каждого объёма находится в неограниченном количестве. Игрок до начала боя может применить на персонажа сколько угодно зелий.
По заданным уровням игроков до начала рейда посчитайте минимальное количество монет, которое необходимо игрокам для допуска к бою.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: N – количество игроков (1 ≤ N ≤ 105) и D – требуемую степень (0 ≤ D ≤ 109).
Во второй строке содержатся N целых чисел Li, разделённых пробелом (1 ≤ Li ≤ 106).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное целое число – минимальную суммарную стоимость изменения уровней.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 2
1 2 3 4 5 | 10 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
