ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1295. Crazy Notions

solution hints, just simple math on modulo
Posted by Md. Shahedul Islam (Shahed) 13 Aug 2015 15:15
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