Last non-zero digit of N! (N factorial).
ACM again =)
Problem: Find out the last non-zero digit of N!.
Solution:
Read this paper first.
You're supposed to understand the paper now or you can stop reading on this blog, period.
Method: change the number to 5-base and then look up the table as the paper suggests.
Here is the code showing the algorithm: base changing and table looking up. But you'd get a 'WA' if you submitted it. Why? Cos the input can be a very large number (ie. 10100). Apparently a 'long long' number used in the code above cannot deal with it correctly.
Remember how to deal with big numbers when you were in your data structure class? Save them in arrays, one index one digit.
Our problem here is to change a big 10-base number to 5-base. In fact, the only computation to the big number is to divide 5. Quite easy.
Here's the final code, enjoy.
PS, had submitted another 2 simple ACMs also: the HTML and 2x mod n = 1
Got several off-by-one bugs. Should have been more careful. :-/
