Discussion @ 1593. Square Country. Version 2 @ Timus Online Judge

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

Posted by Roman Atangulov 28 Apr 2009 02:34

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

Posted by melkiy 28 Apr 2009 16:28

No.
If you TLE read forum for task 1073.

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

Posted by Teacher30 28 Apr 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)) ) ?

Posted by Roman Atangulov 28 Apr 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)) ) ?

Posted by Teacher30 29 Apr 2009 00:33

Is answered in vkontakte.

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

Posted by 3a[3.141592..]Jlu 19 Jun 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

Discussion of Problem 1593. Square Country. Version 2