ADTRI - Editorial

editorial
, , , ,
21

Proof of this Fermat’s theorem can be found here

22

why did you use an array of 10^7 order??

23

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. :frowning:
very tight time limit :frowning:

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 :frowning:

24

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 https://www.codechef.com/viewsolution/8535894

25

i have tried pypy also but still getting TLE although it reduces 1 &2 subtasks time any help?

26

@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.

27

Why do people use cin cout?!

28

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 https://www.codechef.com/viewsolution/8496771 any kind of help is thankful.

29

This problem can also be solved using this:

Solution:
https://www.codechef.com/viewsolution/8314782

4 Likes
30

0.13 time. _ Nice!

1 Like
31

@rahul_mishra01 I used 10^7 array just to avoid overflow as n is about 5*10^6.

32

I’m suprised that the editorialist hasn’t given any proof to the solution. Here is what is missing in all the links provided here.

We know that if p = 4k+1 is prime, than there exist positive integers a, b, such that p = a^2 + b^2. All we have to understand now that p^2 then is the sum of two positive integers, after that we can multiply both of them by n/p and obtain the representation of n.

So, if p = a^2 + b^2, and a > b (they are obvious not equal), take a’ = 2ab, b’ = a^2 - b^2. Than a’^2 + b’^2 = (2ab)^2 + (a^2 - b^2)^2 = a^4 + b^4 + 2 a^2 b^2 = (a^2 + b^2)^2 = p^2. So the assertion is proved.

The other side of the assertion is the consequence of the theorem about the representation of numbers as a sum of two integer squares: we can divide n by prime factors of the type 4k+3 until it contains them, both a and b are divided by these primes too during this process. After that we also eliminate all powers of 2 from n, since 4 divides a^2+b^2 implies that both a and b are divisible by 2. So, in the end we obtain either 1 or the number with prime divisors of the type 4k+1. In the first case there is no representation in sum of two positive squares.

1 Like
33

this is irritating i have done the same thing i m getting 40 points but when i exceede my array to 5*10^6 i get SIGSEGV error anyone plz check my code https://www.codechef.com/viewsolution/8616282

34

Fof all those guys who are getting SIGSEGV declare the array globally of size 5000001 it is because you can declare the array of size not greater than 10^6 in a fuction so declaring it in main function gives u SIGSEGV so you need to declare it globally…!!!
NICE QUESTION…LEARNT A LOT FROM THIS ONE
THANK YOU CODECHEF !!!