#10212 - The Last Non-zero Digit.
|Solution Description: ||Given the high time limit (10 seconds) and the moderate bound on N, it's OK to do this in O(N).|
Multiply all numbers from N to N-M+1 together to get N P M. Of course, this will be extremely large, so after every multiplication, keep taking % 10 while possible to remove trailing zeros, and then take % 1000000000 to keep only the necessary non-zero digits. You need to keep one more digit than the largest digit you multiply by to avoid losing information.
Use longs for all calculations. At the end, output the result % 10.
Watch out for M = 0. Output 1 in this case.
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By