Consider this question…how is the solution given below is working ??
How we arrive at the formula used???
http://www.codechef.com/viewsolution/6391065
You may write the pythagoras theorem as a^{2} + b^{2} = c^{2} and then a^{2} = c^{2} - b^{2}, here a is the given height and c and b being the hypotenuse and the base respectively.
Now there arise two condition first when a is odd and second when a is even for this you may write the factorization of a as
a=2^{a_0}p_1^{a_1}p_2^{a_2}...p_n^{a_n}
Now, to find the number of ways L(a) in which a number a can be the leg (other than the hypotenuse) of a primitive or nonprimitive right triangle is
L(a) = \left\{\begin{matrix} \frac{1}{2}[(2a_1+1)(2a_2+1)...(2a_n+1) - 1] & for a_0 = 0\\ \\\frac{1}{2}[(2a_0-1)(2a_1+1)(2a_2+1)...(2a_n+1) - 1] & for a_0 \geqslant 0 \end{matrix}\right.
Note that L(a)= 1 iff a is prime or twice a prime .
You would note that when a is odd, answer would be just the \frac{1}{2} times the number of divisors of a^2.
Hope this would be of great help to you.
Sorry for replying so late , had to learn a little bit latex before posting this solution. 
1 Like