Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 08.05.2010, 14:36
гость

 
Сообщений: n/a

Разложения на сумму четырех квадратов
Нужно определить количество способов разложения натурального числа на сумму четырех квадратов натуральных чисел. Разложения, в которых разное только размещения слагаемых, считаютса равными.
  #2  
Старый 08.05.2010, 14:47
гость

 
Сообщений: n/a

Ну и что? Тут телепатов нет, говори конкретнее в чем нужна помощь.

Нужно аналитическую формулу вывести? Программу написать? Перебор неприемлимо долго работает? А сколько будет приемлимо?
  #3  
Старый 08.05.2010, 14:52
гость

 
Сообщений: n/a

Ну, нужно написать программу, лимит времени 1 секунда. Да, я пробовал рекурсивный перебор с запоминаниям уже вычисленных значений, немного за долго.
  #4  
Старый 08.05.2010, 14:53
гость

 
Сообщений: n/a

Ограничение на n и ссылку на задачу в студию.
  #5  
Старый 08.05.2010, 14:56
гость

 
Сообщений: n/a

Даю условия, бо скорее всего вы не сможете перейти по ссылке
Упорядоченную четверку натуральных чисел (a, b, c, d) будем называть квадроквадратурой натурального числа N, если выполняется следующее равенство:

a2 + b2 + c2 + d2 = N

Квадроквадратуры, различающиеся порядком следования чисел, считаются различными.

Напишите программу, которая находит количество квадроквадратур заданного натурального числа N.

Технические условия

Входные данные

Входной файл содержит одно натуральное число N (1 ≤ N ≤ 1000000).

Выходные данные

Выведите в выходной файл одно число - количество квадроквадратур числа N.

Информация о задаче
Лимит времени: 1 секунда
Лимит памяти: 64 MB
  #6  
Старый 08.05.2010, 15:46
гость

 
Сообщений: n/a

Попробуйте динамическим программированием решить, должно пройти.
  #7  
Старый 08.05.2010, 15:56
гость

 
Сообщений: n/a

Вы имеете в ввиду вычислять для (N+1) если известно для N? Я про это тоже думал, но для этого тогда нужно знать эти разложения для N, а сохранять их это немножко накладно.
  #8  
Старый 08.05.2010, 15:58
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Попробуйте динамическим программированием решить, должно пройти.
хотя не, сложность O(n^1.5), может и не пройти или впритык.

лучше так - заводите массив, в котором для каждого k будет число пар (a, b), таких что a <= b и a^2 + b^2 = k. Просто двумя циклами создаете.

Потом перебираете все c^2 + d^2, c <= d и прибавляете к ответу число в массиве по индексу n - c^2 - d^2.

Но если n-c^2-d^2 = c^2+d^2, то дважы прибавляете. А в самом конце поделите ответ на два - тогда одинаковые должны, думаю, по одному разу посчитаться.
  #9  
Старый 08.05.2010, 16:00
гость

 
Сообщений: n/a

Сообщение от гость Посмотреть сообщение
Вы имеете в ввиду вычислять для (N+1) если известно для N? Я про это тоже думал, но для этого тогда нужно знать эти разложения для N, а сохранять их это немножко накладно.
да не, сохранить миллион int'ов это немного, всего 4 мб.

А вот O(n^1.5) ~= 1000'000'000 операций на 2-4 Ггц процессорах за одну секунду выполнить может и не удастся.
  #10  
Старый 08.05.2010, 16:22
гость

 
Сообщений: n/a

Спасиба) Ваша идея верна) решения оказалось простым) И можна просто делать цыклы для a, b, c, d без того, что a<=b, c<=d, по таймлиму и так проходить, а считать было бы намного сложнее чем умножать и делить на два.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите выделить сумму полных квадратов гость Математические алгоритмы 4 18.11.2009 21:59
Сплайны по методу наименьших квадратов ziv Вычислительная геометрия 1 26.04.2009 02:50
Нормализация сингулярного разложения (SVD) WW_ Математические алгоритмы (другое) 1 20.02.2009 23:41
Метод четырех русских xz121 Математические алгоритмы (другое) 3 17.10.2008 10:41
Корень из суммы квадратов Michael_K Математические алгоритмы (другое) 19 15.04.2008 01:07