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

Here is the problem link

Reminder: in case of any technical issues, you can use the lightweight website
m1.codeforces.com,
m2.codeforces.com,
m3.codeforces.com.
×

# | User | Rating |
---|---|---|

1 | tourist | 3557 |

2 | Um_nik | 3494 |

3 | Radewoosh | 3344 |

4 | wxhtxdy | 3309 |

5 | LHiC | 3302 |

6 | Benq | 3286 |

7 | mnbvmar | 3274 |

8 | Petr | 3254 |

9 | yutaka1999 | 3190 |

10 | ksun48 | 3170 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 191 |

2 | Radewoosh | 180 |

3 | tourist | 169 |

4 | PikMike | 165 |

4 | antontrygubO_o | 165 |

4 | Vovuh | 165 |

7 | rng_58 | 161 |

8 | majk | 156 |

8 | Um_nik | 156 |

10 | 300iq | 155 |

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

Here is the problem link

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/17/2019 02:07:28 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Probably , you are talking about this topic , Right?

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))`

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

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

https://math.stackexchange.com/questions/5877/efficiently-finding-two-squares-which-sum-to-a-prime