Solved by 1791 users: ...
UserDateAttemptTimeCMSC
zhuojie`13 feb 2008`Python200.0622
zhuojie`16 jan 2008`Python100.0625
V.A.KeRneL`21 feb 2007`Ruby200.0439
V.A.KeRneL`19 feb 2007`Ruby100.0342
Evgenii`04 jul 2010`C++600.0144
ravehanker`18 dec 2005`Python600.0645
Evgenii`04 jul 2010`C700.0146
karthiekc`28 oct 2007`Ruby800.0248
karthiekc`28 oct 2007`Ruby900.0149
sb3ar`12 dec 2007`Ruby200.0449
yangzhe1990`22 feb 2007`FPC200.0150
yangzhe1990`22 feb 2007`FPC300.0150
yangzhe1990`22 feb 2007`FPC400.0150
Robert_Gerbicz`08 jun 2008`C100.0151
melkor217`22 jul 2009`Python100.0753
sb3ar`17 apr 2007`Ruby100.0454
Evgenii`04 jul 2010`C++500.0157
A3AT`14 dec 2004`FPC100.0158
 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

 © acm.mipt DevGroupThe page was generated in 190ms