### Sukarna_Paul's blog

By Sukarna_Paul, history, 10 months ago, ,

How to avoid TLE for this problem as the number of test cases can be 10^4 .

• 0

 » 10 months ago, # |   0 See it https://ideone.com/y9EcZQ. I forget the algorithm name in wiki :)
•  » » 10 months ago, # ^ |   0 Probably , you are talking about this topic , Right?
•  » » 10 months ago, # ^ |   +5 Also according to this theorem we can eliminate all such primes that $p \mod 4 = 3$.
 » 10 months ago, # |   +9 With current TL problem can be solved in time O(t * sqrt(p)). Code
 » 10 months ago, # |   0 I am not sure about the wiki name of this algorithm, may be its name is "One sentence algorithm"But you can solve this problem using simple implementation. Here is the codeAccording to the algorithm : if you check some prime number you found a prime number, if p%4= 1 then it is possible p=a^2+b^2, Otherwise it is not possible. Here 2 is the corner case. Here is the code
 » 10 months ago, # | ← Rev. 8 →   0 Here is my solution for this interesting problem of solving the equation $a^2+b^2=P$. If $P=2$, then the answer is $a = b = 1$. If $P \geq 3$, then $P = (2\times p+1)$ is an odd prime number, where $p \geq 1$. Assume without losing generality that $a = 2 \times k+1$ and $b = 2 \times l$, as $a$ and $b$ cannot have the same odd/even parity. A solution exists if $p$ is an even number and there exists integer numbers $k \geq 0$ and $l \geq 1$ such that $l^2 = p/2 - k(k+1)$. For example, if $P=5$, then $p=2$, $k=0$, $l=1$, $a=1$ and $b=2$. If $P = 7$, then no solution exists as $p=3$ is an odd number. The following is a C++14 implementation of this solution.https://ideone.com/fblLp7
 » 10 months ago, # |   0