### 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 .  Comments (7)
•  » » Also according to this theorem we can eliminate all such primes that $p \mod 4 = 3$.
 » With current TL problem can be solved in time O(t * sqrt(p)). Code
 » 10 months ago, # | ← Rev. 8 →   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