SPOJ.com - Problem CATHETEN

CATHETEN - Shared cathetus (easy)

no tags

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.

catheten

(8 15 17), (15 20 25), (15 36 39), (15 112 113)

Thus F(15) = 4.

Input

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.

Output

For each test case, print F(n) on a single line.

Example

Input:
3
5
10
15

Output:
1
1
4

Constraints

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)

Submit solution!

hide comments

< Previous 1 2 Next >

	aruhanshani: 2020-07-02 05:41:45 this problem will be harder if n can be the cathetus (leg) or ** n can be the hypotenuse (when i think use Fermat's theorem on sums of two squares and bramagupta it seem hard :)) )
	David: 2020-04-01 04:43:30 Francky - Nice problem! =(Francky)=> Many thanks for your appreciation ;-) Last edit: 2020-04-01 13:37:51
	Shashank Srivastava: 2015-03-07 23:18:04 @Francky could you tell me where my code fails? I have checked for all cases I could think of. (Francky) => You have few WA, you're not so far. No other test case is provided. Last edit: 2015-03-08 00:55:34
	Archangel: 2015-03-03 23:07:35 great problem, I learnt from it! THANKS Francky :) (Francky) => You're welcome. Last edit: 2015-03-04 00:49:13
	[Lakshman]: 2015-01-14 04:53:29 Now it is possible to get AC with Python(PYPY). --(Francky)--> Great ;-) Note it was possible before. Now, my old code in PYPY got AC in 0.93s. Last edit: 2015-01-14 07:17:08
	Francky: 2014-07-24 12:57:51 @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. edit(Francky)--> Your code seems to fail only in the end of the range, near 10^9. You should have checked that by your own. And about speed, your f**r method is a bit poor ; if I could choose time for each language, I would certainly gave TLE to such a method. You have, in any case, done a quite good job, you're not so far. Good luck, and keep fun. Last edit: 2014-07-24 15:05:17**
	Puneet Gupta: 2014-07-23 23:16:29 Is the problem having O(1) solution? --ans(Francky)--> No, and the complexity will not be given. Good luck. Last edit: 2014-07-24 07:41:00
	Bhavik: 2014-07-23 15:19:55 @Francky: this might be your easiest problem (atleast for me):) --(Francky)--> Good job. @Mitch : Many thanks for your words. Last edit: 2014-07-24 12:57:34
	Mitch Schwartz: 2014-07-21 17:22:32 @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. In general, you could also try asking for an easier edition of the problem if you think it could still be interesting, possibly for classical or tutorial depending on the problem. This is more constructive than merely calling the problem ugly and poorly prepared, as you have done. (Reply to reply) We often call a problem easier or harder simply based on size of input/constraints compared with allowed time. If problems X and Y are the same except that Y has larger input requiring a more efficient approach, we would generally call Y harder. This does not necessarily mean that problem Y is more challenging to solve, although it is often the case. You have expressed displeasure that ugly trickery (as you call it) is required to pass within the time limit. This implies that you would prefer a more relaxed time limit or smaller input/constraints that would allow a less efficient approach to pass. Hence, an easier version of the problem. Last edit: 2014-07-22 02:31:54
	wellwet: 2014-07-21 11:51:03 @Francky: why WA in my submissions? Tested in PARI, results are the same. PS. Beautiful math-born algo will always give TLE but ugly stupid sieves and the like will bring you AC... So tired of it... --ans(Francky)--> Your "beautiful(?)" can't get a single answer in the given time ; the complexity isn't the awaited... You have many WA in your other code, but good ones too (say 50%). You should improve your confrontation vs PARI or another method. @Francky: I don't try to confrontate (I'm far from it) I just express my point of view. I know that WA is caused by stupid sieve. Naive div counting gets TLE. But math is right and in some sense is beautiful. It's a pity that you chase the speed not math. Many of your problems fall in that category. Time, complexity etc doesn't matter. Only math matters. Ad hoc optimizations and fight for time ruin math beauty. I didn't mean this problem it's the matter of things for pretty any "hard" problem in SPOJ. As a 'golden standard' for good math problem I would choose any Min_25' problem: this is where good algo is born from math. --Francky--> Optimizations are only needed for Python AC, as in many problems here. With a fast language, you don't need any opti. Good luck. (some people like to find opti to get AC, and/or that 0.00s is very hard.) @Mitch: I don't complain about my impossibility to solve the problem. I don't look for easy way for solving. I hate "easy" versions with my whole heart. I just explain my meaning of the phrase "to solve the problem": not to do code trickery but to make a little mathematical discovery. But such solutions will always give TLE. This is it. @Francky: WAs are really strange. I can prove that math behind my solution is right. How did you verify your test-cases? And can you provide me one of "faulty" test-cases? Last edit: 2014-07-21 22:03:51

Submit solution!

Added by:	Francky
Date:	2013-04-19
Time limit:	1.899s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Old problem