Квадраты

[Genrih]

Есть такая задача (попалась на олимпиаде):
По заданному числу S (площадь квадрата) найти количество различных квадратов с целочисленными
вершинами и площадью меньшей или равной S.

Различными считаются квадраты с разными длинами сторон.

Есть два тестовых примера:
Вход:
4
25
Выход:
3
13

_________
Можно, конечно, в одном вложенном цикле пробежаться с условием : сумма квадратов < S , но при
больших S (<10^8), времени уйдет немало.

Есть ли какие-нибудь другие идеи (кроме оптимизации границ циклов)?

[незваный гость]

Если я Вас правильно понимаю:
1) первая вершина имеет координаты $(0, 0)$;
2) Вторая вершина имеет координаты $(a, b)$, причем из различности следует что $a \le b$
3) Площадь такого квадрата равна $a^2 + b^2 \le S$;
4) мы ищем все такие $(a, b)$. Здесь вопрос -- какие квадраты считаются различными -- с различными площадями или различными координатами. Если с площадями -- хреновее... Если с координатами, то:
5) Для данного $а \le \sqrt{S/2}$ мы имеем в кандидаты для $b$ целые в диапазоне $[a, \sqrt{S - a^2}]$. Их количество легко считается. Итого сложность ${\rm O}(\sqrt{S})$.

P.S. Что именно имеется в виду, можно попытаться уточнить, сравнив ответы...

[Genrih]

незванный гость писал(а):

:evil:
Если я Вас правильно понимаю:
1) первая вершина имеет координаты $(0, 0)$;
2) Вторая вершина имеет координаты $(a, b)$, причем из различности следует что $a \le b$
3) Площадь такого квадрата равна $a^2 + b^2 \le S$;
4) мы ищем все такие $(a, b)$. Здесь вопрос -- какие квадраты считаются различными -- с различными площадями или различными координатами

1. не всегда. К примеру, для случая из примера при S=25, в число таких квадратов входит также квадрат с вершинами: (0,1), (1,5), (5,4), (4,0)

Различными считаются квадраты разных именно площадей.

[незваный гость]

Genrih писал(а):

"""1) первая вершина имеет координаты $(0, 0)$;"""
1. не всегда. К примеру, для случая из примера при S=25, в число таких квадратов входит также квадрат с вершинами: (0,1), (1,5), (5,4), (4,0)

Я что-то не понимаю. Тогда мы имеем бесконечно много квадратов площади 1 -- с вершинами $(n, 0)$, $(n+1, 0)$, $(n, 1)$, $(n+1, 1)$. Описанный Вами квадрат я приводил к виду $(0, 0)$, $(1,4)$, $(5,3)$, $(4,-1)$.

Вот с различием квадратов по площади хреновее, как и было сказано...

[незваный гость]

Из Википедии:

Цитата:

A positive integer can be represented as a sum of two squares precisely if its prime factorization contains no odd powers of primes of the form 4k+3.

Дает некоторый простор для размышлений об алгоритме -- например, использующий решето Эратосфена...

Впрочем, я сомневаюсь, что это самый быстрый способ ответа на вопрос. Если $n = a^2 + b^2$, то можно без ограничения общности считать, что $a \leqslant b \leqslant \sqrt{n/2}$. Таким образом организовав двойной цикл по $a$ и $b$, мы все равно имеем линейное время. На Python:

import math, time

def squares(s):
   bitmap = [0 for ix in xrange(0, s+1)] ## инициализируем массив нулями

   ## для описанного диаапазона a
   ## / -- выдает результат с плавающей точкой
   for a in xrange(int(math.sqrt(s/2)) + 1):
      b = a
      n = a**2 + b**2
      ## внутренний цикл по b -- ограничен проверкой n
      ## одна из причин -- мы не очень точно считаем верхнюю границу a
      while n <= s:
         bitmap[n] = 1
         b += 1
         n = a**2 + b**2

   return sum(bitmap)-1 ## because 0 is always marked and is not a valid square

def test(s):
   start = time.clock()
   ns = squares(s)
   end = time.clock()
   print "%d: %d squares (%.3f secs)" % (s, ns, end - start)

test(4)
test(25)
test(1000000)
test(10000000)
test(100000000)

результат:

4: 3 squares (0.000 secs)
25: 13 squares (0.000 secs)
1000000: 216341 squares (0.757 secs)
10000000: 1985459 squares (7.318 secs)
100000000: 18457847 squares (90.713 secs)

Некоторая нелинейность (для $10^8$) связана с управлением скоростью процессора (защита от перегрева).

Конечно, это все еще можно пытаться оптимизировать. Например, подсчитывая заранее квадраты. Но, вроде, и так не плохо...

[Genrih]

незванный гость писал(а):

... Описанный Вами квадрат я приводил к виду $(0, 0)$, $(1,4)$, $(5,3)$, $(4,-1)$.

Да, ето я работал в первом квадранте.

[Genrih]

Спасибо.
Да, имея в виду $ a \leq b \leq \sqrt{n/2}$, время линейно. Python'ом не владею, но суть ясна.

незванный гость писал(а):

Вот с различием квадратов по площади хреновее, как и было сказано...

Не, квадраты одной площади не считаем. Нас не волнуют квадраты одной площади, но с разными координатами. Так их будет, действительно, не счесть.
Именно количество квадратов с различными площадями, меньшей $S$.
На С++ :

#include <iostream>
#include <math.h>
using namespace std;

__int64 s, b;
int n;

void solve()
{

 int i, j;
 scanf ("%I64d", &s); 

n = int(sqrt(double(s)));
b=n; //сразу считаем квадраты с целой длиной стороны

for (i = 1; i < int(sqrt(s/2))+1; i++)
for (j = i; j < n; j++)
{ 
 double q = sqrt(double(i*i + j*j));
 if ((q - int(q)) && (i*i + j*j) < s )  b++ ; // + проверка, не будет ли число точным
}                                                 // квадратом (мы их уже посчитали)
 printf("%I64d\n", b);
}


void main()
{
 solve();
}

Результат:

Input:
4
25
1000000
10000000
100000000

Output:
3
13
39266
3926286
39265946

Время пока не могу засечь - просто не знаю как. Но ето совсем неплохо даже (по скорости).
В Вашем коде, как вижу, нет условия точных квадратов суммы $a^2+b^2$, но даже в етом случае в Ваших результатах числа меньше по величине.

[незваный гость]

Genrih писал(а):

В Вашем коде, как вижу, нет условия точных квадратов суммы $a^2+b^2$

Я -- хитрый, у меня $a$ с нуля начинается -- это и дает полный квадрат. А чтобы не было проблем, я квадрат нулевой площади в конце выкидываю.

И еще: я могу ошибаться, но мне кажется, Вы не учитываете возможности неоднозначного разложения числа в сумму квадратов. Например, $25 = 0^2 + 5^2 = 3^2 + 4^2$.

[Genrih]

незванный гость писал(а):

:evil:
Я -- хитрый, у меня $a$ с нуля начинается -- это и дает полный квадрат. А чтобы небыло проблем, я квадрат нулевой площади в конце выкидываю.

Ага, теперь понятно. А случай с числами Пифагора ?

[Genrih]

незванный гость писал(а):

:evil:
И еще: я могу ошибаться, но мне кажется, Вы не учитываете возможности неоднозначного разложения числа в сумму квадратов. Например, $25 = 0^2 + 5^2 = 3^2 + 4^2$.

Для етого в цикле условие:

if ((q - int(q)) && (i*i + j*j) < s )

Первое как раз и дает условие НЕцелостности $\sqrt{a^2+b^2}$. В итоге у нас и целые посчитаны и неоднозначности/повторений нет

[незваный гость]

Заметьте, я считаю не сразу. Вместо этого я записываю единицу в карту (bitmap) чисел. Поэтому, сколько бы раз число не встретилость, в карте всегда либо ноль, либо единица. А потом я суммирую эти единицы, и получаю ответ.

Вы несколько напрасно называете числа с неоднозначным разложением числами Пифагора. Да, все тройки раскладываются неоднозначно, но не все, кто раскладывается неоднозначно -- Пифагоровы тройки. $325 = $ $1^2 + 18^2 =$ $6^2+17^2 = $ $10^2+15^2$.

А Python я Вам настоятельно рекомендую. Весьма пользителен, когда надо понять, что делаешь.

[незваный гость]

Genrih писал(а):

Первое как раз и дает условие НЕцелостности

Условие нецелости у Вас ненадежное. Из-за ошибок округления возможны варианты в обе стороны.

Но главное -- смотрите пример выше.

2  25
3  325
4  1105
5  4225
6  5525
8  27625
9  71825
10 138125
12 160225
16 801125
18 2082925
20 4005625
24 5928325
32 29641625
36 77068225

Первая колонка -- количество способов. Вторая колонка -- наименьшее число, разложимое таким количеством способов.

[Genrih]

незванный гость писал(а):

Вы несколько напрасно называете числа с неоднозначным разложением числами Пифагора. Да, все тройки раскладываются неоднозначно, но не все, кто раскладывается неоднозначно -- Пифагоровы тройки. $325 = $ $1^2 + 18^2 =$ $6^2+17^2 = $ $10^2+15^2$.
А Python я Вам настоятельно рекомендую. Весьма пользителен, когда надо понять, что делаешь.

Да, ето неправильно. Вот где оказывается у меня перебор.
Спасибо за заметки и совет! Дальше ясно.

добавлено:

незванный гость писал(а):

Условие нецелости у Вас ненадежное. Из-за ошибок округления возможны варианты в обе стороны.

Но главное -- смотрите пример выше

Да его (условия) уже и не будет

[evgeny]

Если это была олимпиада по программированию, то там часто применяется метод с предвычислениями.
Вы заранее ситаете ответы для $n=k\cdot10^4,\quad k=1,2,3,...,10^4$
После этого остается найте колво чисел представивых ввиду суммы квадратов в интервале $(k\cdot 10^4, k\cdot10^4+A), \quad A < 10^4$
для этого достаточно проверить все точки (из первого квадранта) в кольце $\sqrt{k\cdot 10^4}\le R \le \sqrt{k\cdot10^4+A}$, а из примерно $\frac{\pi}{4}A$.

Таким образом с массивом из $10^4$ констант для любого $n<10^8$ программа будет работать примерно как для $n=10^4$.
Это уже более чем приемлимо по времени (для $n=10^8$ программа на С работает $3.5$ секунды)


Более того если писать программу правильно, то для $n=10^8$ она работает $0.6$ секунды
(что не удивильно - рассматривается всего $\frac{\pi}{8}10^8$ точек, а частота процессора $3.0$GHz)

[незваный гость]

Простите, правильно ли я понимаю, что Вы не включаете время построения таблицы во время работы программы? (То есть, Вы сначала пишете подсобную программу, которая строит Вам таблицу -- за любое время -- а потом Вы просто пользуетесь этой таблицей в "сдаваемой" программе)?

Коли Вы приводите времена, то может быть Вы найдете возможным показать нам программу? (без таблицы, разумеется:) )