Ctrl K

Номера с квадратными произведениями

Сложная
Дан массив values, элементы которого пронумерованы **с единицы**. Выберите непустую группу номеров так, чтобы произведение **любых двух** выбранных номеров было точным квадратом (группа из одного номера подходит всегда). Верните наибольшую возможную сумму элементов выбранной группы.
Пример 1
values=[3, 1, 4, 6, 2, 5, 2, 8] → 9

Номера 1 и 4: 1·4 = 4 — квадрат, сумма 3 + 6 = 9. Номера 2 и 8: 2·8 = 16, сумма 1 + 8 = 9. Номера 1 и 4 нельзя объединить с 2 и 8 (1·2 = 2 — не квадрат). Ответ 9.

Пример 2
values=[2, 5, 7] → 7

Никакие два номера не дают квадрат, поэтому берём один элемент — самый большой, 7.

Пример 3
values=[1, 1, 1, 1, 1, 1, 1, 1, 1] → 3
Ограничения
  • 1 ≤ len(values) ≤ 10⁴
  • 1 ≤ values[i] ≤ 10⁹
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамая большая группа с общими делителями СложнаяСобрать единицу СложнаяГорода, связанные большими делителями СложнаяБлижайший взаимно простой предок СложнаяРазличные НОД наборов Сложная
загружаем Python…
Вход
values=[3, 1, 4, 6, 2, 5, 2, 8]
Ожидается
9

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 64 теста на сервере, включая скрытые.