<PREV Problem:
NEXT>
Solved by 1791 users: ...
UserDateAttemptTimeCMSC
zhuojie13 feb 2008Python200.0622 
zhuojie16 jan 2008Python100.0625 
V.A.KeRneL21 feb 2007Ruby200.0439 
V.A.KeRneL19 feb 2007Ruby100.0342 
Evgenii04 jul 2010C++600.0144 
ravehanker18 dec 2005Python600.0645 
Evgenii04 jul 2010C700.0146 
karthiekc28 oct 2007Ruby800.0248 
karthiekc28 oct 2007Ruby900.0149 
sb3ar12 dec 2007Ruby200.0449 
yangzhe199022 feb 2007FPC200.0150 
yangzhe199022 feb 2007FPC300.0150 
yangzhe199022 feb 2007FPC400.0150 
Robert_Gerbicz08 jun 2008C100.0151 
melkor21722 jul 2009Python100.0753 
sb3ar17 apr 2007Ruby100.0454 
Evgenii04 jul 2010C++500.0157 
A3AT14 dec 2004FPC100.0158 
Languages
C++
885
FPC
391
C
325
Java
94
Kylix
60
Python
24
Ruby
21
Perl
6
Scheme
5
Lua
3
Haskell
1
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 = 34.204.176.125