VK Cup 2022 - Отборочный раунд (Engine) |
---|
Закончено |
Дано множество $$$a_1, a_2, \ldots, a_n$$$ из различных положительных целых чисел.
Назовем квадратностью целого числа $$$x$$$ количество точных квадратов среди чисел $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$.
Найдите максимальную квадратность среди всех целых чисел $$$x$$$ от $$$0$$$ до $$$10^{18}$$$ включительно.
Напомним, что точными квадратами являются числа вида $$$t^2$$$, где $$$t$$$ — неотрицательное целое число. Наименьшими точными квадратами являются $$$0, 1, 4, 9, 16, \ldots$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — размер множества.
Вторая строка содержит $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots, a_n$$$ в возрастающем порядке ($$$1 \le a_1 < a_2 < \ldots < a_n \le 10^9$$$) — само множество.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$50$$$.
Для каждого набора входных данных выведите одно целое число — наибольшее возможное количество чисел среди $$$a_1 + x, a_2 + x, \ldots, a_n + x$$$, являющихся точными квадратами, для некоторого $$$0 \le x \le 10^{18}$$$.
451 2 3 4 551 6 13 22 97110052 5 10 17 26
2 5 1 2
В первом наборе входных данных при $$$x = 0$$$ в множестве будут два точных квадрата — $$$1$$$ и $$$4$$$. Более двух точных квадратов получить нельзя.
Во втором наборе входных данных при $$$x = 3$$$ множество примет вид $$$4, 9, 16, 25, 100$$$, то есть все его элементы станут точными квадратами.
Название |
---|