<PREV Problem:
NEXT>
Solved by 1788 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Three squares

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:
10
SAMPLE OUTPUT #1:
1

SAMPLE INPUT #2:
100
SAMPLE OUTPUT #2:
15

Author:
Voroztsov Artem

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 210ms

SW soft NIX
ID = 54.224.164.166