Номер разбиения `n` на сумму трех квадратов (быстрый алгоритм)

Question

Несколько лет назад я обнаружил интересную проблему программирования:
«Найти номер разбиения n на сумму трех квадратов с n < 10^9 и ограничением в 1 секунду».

Вопрос: Кто-нибудь знает, как решить эту проблему с заданными ограничениями?
Я думаю, что это может быть сделано исключительно с асимптотической сложностью времени быстрее, чем O(n) только? Есть ли какой-то умный математический подход или это инженерная задача оптимизации кода?

Я нашел некоторую информацию о https://oeis.org/A000164,, но в разделе FORMULA
есть O(n) -альго. (потому что нам нужно найти все делители каждого n-k^2 числа для вычисления e(n-k^2)) и O(n) -algo в разделе MAPLE.

Answer 1

Да.Сначала вычислите число n - z^2 в простые числа, разложите простые числа в гауссовы сопряженные и найдите различные выражения для расширения и упрощения, чтобы получить a + bi, который затем можно повысить, a^2 + b^2.Мы можем исключить любого кандидата n - z^2, который содержит простое число формы 4k + 3 с нечетной степенью.

Это основано на выражении чисел как гауссовых целочисленных сопряженных.(a + bi)*(a - bi) = a^2 + b^2.См https://mathoverflow.net/questions/29644/enumerating-ways-to-decompose-an-integer-into-the-sum-of-two-squares и https://stackoverflow.com/a/54839035/2034787