![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.2){kind=small}
![[info]](http://l-stat.livejournal.com/img/community.gif?v=92.2){kind=small}
Каждое целое неотрицательное число можно разложить в сумму из 4 квадратов целых чисел.
Это известное утверждение. Но мне хочется узнать сколькими способами можно разложить в сумму 3 квадратов целых чисел известное мне натуральное число? А может быть известно что-то о распределении чисел, которые не представляются в виде суммы 3 квадратов?
P.S. Я не специалист в теории числе и смежных областях. Поэтому даже не представляю, насколько сложны данные вопросы.
P.S.S. В принципе, мне интересно так же, сколькими способами натуральное число раскладывается в сумму двух квадратов целых чисел. Или хотя бы условия, когда нат. число не раскладывается в сумму 2 квадратов.
May 19 2008, 16:11:25 UTC 4 years ago
В виде суммы двух квадратов представимы все числа, в разложение которых на простые множители все простые вида 4k+3 входят в четных степенях.
Количество способов представить число в виде суммы двух квадратов есть разность между количеством делителей вида 4n+1 и 4n+3. В виде суммы четырех квадратов --- количество делителей, не кратных 4. (В зависимости от того, считать ли перестановки слагаемых за разные представления, появляются множители).
May 19 2008, 21:35:55 UTC 4 years ago
May 20 2008, 05:55:57 UTC 4 years ago
May 20 2008, 06:29:10 UTC 4 years ago
Мне-то формула 17 гораздо больше нравится.
May 19 2008, 16:18:03 UTC 4 years ago
May 19 2008, 17:09:39 UTC 4 years ago
May 19 2008, 22:19:53 UTC 4 years ago
September 8 2008, 16:23:59 UTC 3 years ago
June 6 2008, 14:44:12 UTC 3 years ago
December 21 2008, 14:12:12 UTC 3 years ago
. . .
April 27 2009, 20:01:43 UTC 3 years ago
Есть число N <= 10^15. Нужно узнать, можно ли его представить в виде суммы 2 квадратов. Ограничение по времени 1с, поэтому асимптотика алгоритма должна быть меньше O(sqrt(N))...
Кто-нибудь знает, как решить?
Anonymous
June 30 2009, 09:11:44 UTC 2 years ago
* методом аткина находишь простые в интервале (1,sqrt(N))
* выбираешь из них только те, что вида 4k+3 (%4 == 3)
* проверяешь в каких степенях они входят в нужное число N
Anonymous
November 15 2010, 22:38:02 UTC 1 year ago
Всё проще
Сорри за некроманство, конечноЗначит, переберем A = 1..sqrt(n)
A^2 + B^2 = C → B^2 = C - A^2
запишем в первый список пару A^2
во второй B^2
после рассмотрения всех A перевернём второй список, становится ясно, что оба списка во-первых в одну сторону отсортированы, во-вторых, наличие пары одинаковых даёт положительный ответ на вопрос задачи, дальше очевидный метод двух указателей и вуаля O(sqrt(n))