|
|
back to boardThanks in advance 1) If N==a^2, that is if N is a full square, the answer is 1
2) Try N = a^2 + b^2. Brute force, but "clever" brute force.
This is the most expensive part of the algo
3) N is NOT a sum of 3 squares <=> N=(8k+7)*4^m
This is a fast step, about O(log(N))
4) Lagrange theorem states: each number may be presented as a sum of 4 squares: N = a^2 + b^2 + c^2 + d^2
So if the upper three cases fails, the answer will be 4. Nice algorithm! Thank you, melkiy.
But you can find N = a^2 + b^2 without brute-force. I considered this case by facrotizing N to primes and using Ferma-Euler theorem. How to apply Ferma-Euler theorem to this problem ? No brute force. Moreover, we don't need to find the sum of squares, we need just answer.
find factorization of N = L*m^2, where L is not divisible by p^2 for p is prime.
if L==1 then answer = 1
if L has no prime divisors of the form 4*t+3 then answer = 2 (Fermat)
if N != (8*t+7)*4^k then answer = 3 (Legendre)
else answer = 4 Thank, every body.
+1 Got AC.
Edited by author 22.01.2013 20:14 If L has prime divisors of the form 4*t+3，the answer may be 2,too.
How to explain this question？ Fermat's theorem says that if N=a^2+b^2, then L hasn't prime divisors of the form 4t+3, and back. A simpler to calculate approach is just to check if the prime decomposition contains no ODD powers of primes that can be expressed as 4*t+3, in which case the answer is two. |
|
|
