Can you please explain how to get this formula : prime factor must be of form 4k+1 ? I came up with it using my own logic but the logic was wrong. I somehow, by mistake, got the formula and solved it. I need to know how I could have derived it. Can you give some pointers or links?
@dragonemperor
It’s euclid’s theorem. We know for any m and n(there are some conditions),the 3rd arm of pythagorean triples will be (m^2+n^2). If you look closely, N always will be the 3rd arm of pythagorean triples of a right angle.
1 Like
@dragonemperor refer to this Fermat's theorem on sums of two squares - Wikipedia
It comes from the same theorem! When we check if a number can be written as sum of two squares, we check if it has a prime factor of the form 4k+1. So it doesnt matter whether it is N^2 or N as N^2 will have a factor N which maybe prime of form 4k+1.
1 Like
Another Approach is to find all primitive pythagoereian triplets using euclid’s method and then prime factorizing ‘N’ and seeing if any prime factor is a part of a primitive pythagoereian triplet.
1 Like
Precomputation…
Since we know that the n (given length) will always be the hypotenuse.If we pre-compute all the pythagorian triplet till the maximum value of n then we can easily check whether there is a pythagorian triplet of length equal to n or not. Thus this can be done in O(1) time… to check whether pythagorian triplet exist for given ‘n’ or not…
1 Like
here is my solution. I have done the same thing as mentioned in the editorial above. However, am stuck at 40 points. Someone plz help. 
@agarwl96 some suggestions. use printf scanf instead of cin cout. also in second loop to avoid checking modulo 4 everytime, start iterating from 5 and every 4th element from there (i=5,i+=4). should reduce some time CodeChef: Practical coding for everyone
Using cin/cout with fast I/O gave TLE for the last sub-task : 40 points
However, using scanf/printf for the otherwise same code got accepted : 100 points
Not cool.
I also thought of the same solution, but could not implement because of a reason:
8 = 2^2 + 2^2, and 2 is the only prime factor of 8 which doesn’t satisfy 4K+1. Please help me in understanding the concept.
I observed the pythagorean triplets as 4k+1 (pattern) during the contest and solved the problem. CodeChef: Practical coding for everyone
But what is the logic behind 4k+1 . Any mathematical proof?
@avidcoder Refer to these two links 1. Pythagorean triple - Wikipedia
2. Fermat's theorem on sums of two squares - Wikipedia
@atulshanbhag No proof in any of those links. I think this condition dont have any proof. We should observe patterns and make assumptions. it is like mathematical induction.
hell, i did the same and get tle in last subtask. using java fast I/O. from fast I/O i mean Buffered reader and writer something like that. 
very tight time limit
also i have O(sqrt(n)) complexity for prime factorization and checking that (n-1) % 4 == 0 or not…
time limit should be more flexible… I think
i did exactly same but still getting TLE in last subtask . i am using python and tried everything to reduce time .please help anyone.here is my solution CodeChef: Practical coding for everyone
@avidcoder the proof deals with concepts of congruences, residues and quadratic fields. I have read this proof in the book ‘an introduction to number theory’ by g.h hardy and the proof is very easy to understand if you know about congruences and residues.
I have done the same thing as mentioned above but somehow it is still getting only 40 points .I even used pollard’s rho for int greater than 10^6 and sieve otherwise and i am ruling out primes directly with a binary search .
Where is my code taking time CodeChef: Practical coding for everyone any kind of help is thankful.