2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Квадраты
Сообщение21.05.2006, 20:35 
Аватара пользователя
Есть такая задача (попалась на олимпиаде):
По заданному числу S (площадь квадрата) найти количество различных квадратов с целочисленными
вершинами и площадью меньшей или равной S.

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

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

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

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

 
 
 
 
Сообщение21.05.2006, 22:17 
Аватара пользователя
:evil:
Если я Вас правильно понимаю:
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. Что именно имеется в виду, можно попытаться уточнить, сравнив ответы...

 
 
 
 
Сообщение21.05.2006, 22:27 
Аватара пользователя
незванный гость писал(а):
: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)

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

 
 
 
 
Сообщение22.05.2006, 04:22 
Аватара пользователя
:evil:
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)$.

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

 
 
 
 
Сообщение22.05.2006, 07:50 
Аватара пользователя
:evil:
Из Википедии:
Цитата:
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$) связана с управлением скоростью процессора (защита от перегрева).

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

 
 
 
 
Сообщение23.05.2006, 01:33 
Аватара пользователя
незванный гость писал(а):
... Описанный Вами квадрат я приводил к виду $(0, 0)$, $(1,4)$, $(5,3)$, $(4,-1)$.

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

 
 
 
 
Сообщение23.05.2006, 01:34 
Аватара пользователя
Спасибо.
Да, имея в виду $ 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$, но даже в етом случае в Ваших результатах числа меньше по величине.

 
 
 
 
Сообщение23.05.2006, 02:13 
Аватара пользователя
:evil:
Genrih писал(а):
В Вашем коде, как вижу, нет условия точных квадратов суммы $a^2+b^2$

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

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

 
 
 
 
Сообщение23.05.2006, 02:20 
Аватара пользователя
незванный гость писал(а):
:evil:
Я -- хитрый, у меня $a$ с нуля начинается -- это и дает полный квадрат. А чтобы небыло проблем, я квадрат нулевой площади в конце выкидываю.

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

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


Для етого в цикле условие:
Код:
if ((q - int(q)) && (i*i + j*j) < s )


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

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

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

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

 
 
 
 
Сообщение23.05.2006, 02:41 
Аватара пользователя
:evil:
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

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

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

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

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

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

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

 
 
 
 
Сообщение23.05.2006, 04:20 
Если это была олимпиада по программированию, то там часто применяется метод с предвычислениями.
Вы заранее ситаете ответы для $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)

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

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

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group