CATHETEN - Shared cathetus (easy)
For any integer n, we define F(n) as the number of ways in which n can be the cathetus (leg) of a Pythagorean triangle. For example, there is exactly four Pythagorean triangles with 15 as a length for a cathetus.
(8 15 17), (15 20 25), (15 36 39), (15 112 113)
Thus F(15) = 4.
The first line of input contains an integer T, the number of test cases.
Each of the next T lines contains a single integer n.
For each test case, print F(n) on a single line.
Input: 3 5 10 15
Output: 1 1 4
0 < T < 10^5 0 < n < 10^9
For your information, my C code ran in 0.08s, whereas my python3 one ran in 0.90s. (Edit 2017-02-11, after compiler changes)
@Francky could you tell me where my code fails? I have checked for all cases I could think of.
great problem, I learnt from it! THANKS Francky :)
Now it is possible to get AC with Python(PYPY).
@wellwet : if I find some minutes, I'll give you a small c-exemple where your code fails ; but you should be able to do so by your own.
Is the problem having O(1) solution?
@Francky: this might be your easiest problem (atleast for me):)
@wellwet, beauty is subjective, and that sounds like sour grapes to me. If you think the required solution is too ugly, why not just refrain from submitting to the problem? It's as if you submitted solely because you wanted to complain. Francky is good about giving detailed constraints, which lets you get a pretty good idea of whether your solution is fast enough before submitting. And he also puts a lot of thought into choosing constraints that are reasonable.
@Francky: why WA in my submissions? Tested in PARI, results are the same.
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Pascal and C is different language!