if {(1^n + 2^n + 3^n + 4^n) % 10} is equal to 0, then we find 1 zero.
if {(1^n + 2^n + 3^n + 4^n) % 100} is equal to 0, then we find 2 zeros.
and so on....

now, how to calculate {(1^n + 2^n + 3^n + 4^n) % 10}:

Look,
 {(1^n + 2^n + 3^n + 4^n) % 10}
=((1^n % 10) + (2^n % 10) + (3^n % 10) + (4^n % 10)) % 10   [simple modulo equivalencies]

now,
 (4^n % 10)
= ((((((4%10)*4)%10)*4)%10)*4)%10 . . . . . . . (n times)    [(4%10), then multiply by 4, then mod 10, loop for n times]
similarly for (2^n % 10) and (3^n % 10).   No need for 1, because (1^n % 10) is always 1.

In this way, calculate the rusult of {(1^n + 2^n + 3^n + 4^n) % m} for m = 10, 100, ans so on...  and count zeros... :)


** to know more about modulo equivalencies,
http://en.wikipedia.org/wiki/Modulo_operation

** solution C++:
(don't see the solution before trying, at first try yourself)

http://github.com/shahed-shd/Online-Judge-Solutions/blob/master/Timus-Online-Judge/1295.%20Crazy%20Notions.cpp


Edited by author 13.08.2015 15:51

Edited by author 13.08.2015 23:02