Ввести произвольную последовательность (не обязательно кортеж) натуральных чисел, не превышающих 1000000. Вывести, сколько среди них различных чисел, являющихся суммой трёх квадратов.
Пояснение. Поскольку входная последовательность обрабатывается eval(), она может быть, например, такой: (1+i%10 for i in range(100000)), в этом случае ответ — тоже 3
3, 4, 2, 9, 1, 5, 6, 7, 8, 3, 6
3
(это 1+1+1, 1+1+4 и 1+4+4)
(нажмите «Комментарии» в шапке страницы, чтобы прочитать спойлер)
Кажется, в имеющихся условиях единственный быстрый способ — это составить множество сумм трёх квадратов (с учётом ограничения сверху, т. к. в исходной последовательности есть максимальное число
) и просто взять размер его пересечения с исходной последовательностью.
Множество сумм трёх квадратов:
Обозначим наибольший элемент последовательности M
Поскольку нас интересует сумма, слагаемые упорядочим по неубыванию
Первое слагаемое — квадрат числа i в диапазоне от 1 до $$sqrt(M)$$
Второе слагаемое — квадрат числа j в диапазоне от i до $$sqrt(M-i^2)$$ (потому что первое слагаемое уже $$i^2$$)
Третье слагаемое — квадрат числа k в диапазоне от j до $$sqrt(M-i^2-j^2)$$ (потому что первые два слагаемых уже $$i^2+j^2$$)