|Online MIPT programming contest||РУССКИЙ|
Time limit: 3 seconds
The Waring hypothesis states that every non-negative integer may be represented as a sum of K^2 exact K-th powers of non-negative integers. Hilbert proved this fact in 1907; simplier proofs were given by Hardy, Littlewood and Vinogradov, and in 1942 Linnik found an elementary proof.
For K=2 it follows that every non-negative integer is a sum of four squares. We shall not verify this statement, but insted determine the number of integers in the range 0...n that may not be represented as a sum of three squares.
Input consists of a single positive integer n<10000.
SAMPLE INPUT #1:|
SAMPLE OUTPUT #1:
SAMPLE INPUT #2:|
SAMPLE OUTPUT #2:|
© acm.mipt DevGroup
The page was generated in 200ms