I figured out a solution for problem Div2C. Given a number n , we have to find its other two Pythagorean Triplets.
My approach was as follows:
I stored the factors of n in a vector. Since we have n*n to deal with, I basically decomposed n*n into all possible combinations of any two of (n*n)'s factors p,q such that p*q = n*n
now, a*a +n*n = c*c
=> n*n = (c-a)*(c+a) = p*q
Now assuming min(p,q) = c-a and max(p,q) = c+a, I just checked if the Pythagorean equation is satisfied. My code
What I still can't figure out in my own code is how my solution gives a correct answer if n is a hypotenuse. I have not handled the case x*x + y*y =n*n. My code seems to prove that if x*x + y*y = n*n, then there always exists a,b such that a*a + n*n = b*b. Simply speaking, hypotenuse of any right angled triangle is always cathetus of some other right triangle. Does this always hold true or is there a counter case. A proof from someone would be really helpful. Thanks :)
consider this case -> 3 , 4 , 5
Yes for 5 as hypotenuse ... my solution gives 12 5 13 where 5 is a cathetus. That is exactly what I want to be proved .. hypotenuse of one right triangle is cathetus of another
For each n ≥ 3 exist numbers x, y such that x2 + n2 = y2 so you can consider that n is length of cathetus.
If n is odd :
and 
If n is even
and 
As you can see at least one solution always exists.
OK now I get it. Thanks for the explanation.
x*x + y*y = (y + a)*(y + a) , where x is already given
on solving, y = ( (x*x)/a -a )/2 ,
if x = odd , put a = 1, y = ( (x*x) — 1 )/2 ; // always give solution
// u can also try for any other odd no. for smaller solutions.
if x = even , put a = 2, y = ( (x*x)/4 — 1 ) ; // always give solution
// u can also try for any other even no. for smaller solutions.
Auto comment: topic has been updated by CSGO_is_life (previous revision, new revision, compare).
Solution to Pythagorean Triplets are always in the form (C=a^2+b^2,A=a^2-b^2,B=2*a*b). Lets talk about solutions with a and b being co-primes (since you can multiply anything with these numbers to make more solutions eg. {3,4,5}*2 = {6,8,10}).
Since a and b are co-primes it means a and b has might have different parity. Thus a^2+b^2 can be odd, and since you can get every odd number from some x^2-(x-1)^2 where a=x,b=x-1, you have your proof!
Wow, great solution. Two things I learnt:
Thanks a lot for the analysis.
I actually didn't see this solution during the contest. Sometimes, it's really funny how I complicate things. There was once an easy problem about queries that could be solved by observing that they could all be done offline in any order, and I got it Accepted with a very silly Lazy Segment Tree solution!
For this problem:
I know that every odd prime p can be a leg in some right triangle, so the high-level-idea was to find a primitive triangle having p as a leg where p is the smallest odd prime dividing n, and then scale it upwards. Cases where n = 2k for k > 1 are easily taken care of by scaling (3, 4, 5) by
.
We want to find x and y such that p = x2 - y2, and we want x and y to be coprime. We can shoot two birds with 1 stone by observing that consecutive integers are coprime, and the difference of consecutive squares can yield whatever odd number we want. So, basically, p = (y + 1)2 - y2 = 2y + 1 and thus
. So yeah, you have your x and your y now. The other legs are 2xy and x2 + y2.
So now that you've generated the primitive tuple (p, 2xy, x2 + y2), you just have to scale it up
.
Before I came up with this solution, I was doing something with the factorization of n and using that Brahmagupta-Fibonacci stuff :P. I felt really silly after the contest.
Yes, the x2 — y2, 2*x*y, x2 + y2 would not have occurred to me during the contest. Near the end of the contest, I was on the verge of submitting a code that handled n as hypotenuse case separately because I wasn't able to prove if my solution gave the right answer for all n as hypotenuse. Now I realize that there always exists a solution for the equation x*x + n*n = y*y. Great analysis and thanks :)