Discussion @ 1132. Square Root @ Timus Online Judge

To those who want to solve the problem without using too much math knowledge

Posted by gojiajunchao 2 Jun 2008 20:37

First of all, K is large but the range of n is small (<=32767 and is prime);
So we can process the query with same n at the same time.

And use brute-force method;

Note if there are solutions there are exacly two solutions.

x and n-x ((n-x)^2=x^2(mod n));

Re: To those who want to solve the problem without using too much math knowledge

Posted by Chmel_Tolstiy 3 Jun 2008 02:39

very nice :)

Re: To those who want to solve the problem without using too much math knowledge

Posted by Isidro 25 Oct 2011 02:25

Can you explain me that better, I don't understand your idea.

Discussion of Problem 1132. Square Root