Обсуждение @ 1593. Квадратная страна. Версия 2 @ Timus Online Judge

Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано Roman Atangulov 28 апр 2009 02:34

Re: Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано melkiy 28 апр 2009 16:28

No.
If you TLE read forum for task 1073.

Re: Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано Teacher30 28 апр 2009 20:09

Roma, O(sqrt(n)) is good time to find a, b : a^2 + b^2 = n
My O(sqrt(n)) solution gets AC in 0.25 sec.

-------------------
Sergey Kopeliovich

Re: Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано Roman Atangulov 28 апр 2009 21:17

[code deleted]

-------------------

Вот это получает

Roman Atangulov 1593 C++ Time limit exceeded 13 1.046 137 KB

Edited by author 28.04.2009 21:22

Edited by author 29.04.2009 14:21

Re: Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано Teacher30 29 апр 2009 00:33

Is answered in vkontakte.

Re: Does this need fast factorization (faster than O(sqrt(N)) ) ?

Послано 3a[3.141592..]Jlu 19 июн 2009 17:13

I know O(N^0.5) algo, but I use array[N] :(
Please tell me some ideas, how to solve this task without array? Thanks

Обсуждение задачи 1593. Квадратная страна. Версия 2