Sukarna_Paul's blog

By Sukarna_Paul, history, 7 days ago, In English,

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

Here is the problem link

 
 
 
 

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

See it https://ideone.com/y9EcZQ. I forget the algorithm name in wiki :)

»
7 days ago, # |
  Vote: I like it +9 Vote: I do not like it

With current TL problem can be solved in time O(t * sqrt(p)). Code

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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 code

According 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

»
6 days ago, # |
Rev. 8   Vote: I like it 0 Vote: I do not like it

Here is my solution for this interesting problem of solving the equation $$$a^2+b^2=P$$$.

  1. If $$$P=2$$$, then the answer is $$$a = b = 1$$$.

  2. 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