Internet Problem Solving Contest

IPSC 2006

Solution to Problem D – Digital Calculator

The solution of this problem has (obviously) two parts:

How to find the last L digits of N factorial? If you look closely at the inputs you will find out that we don't need a lot of digits. The last digits of factorials of large numbers are zeroes. The larger the number is, the more zeros its factorial has. The easiest solution is simply to compute the factorials modulo 10L by multiplying all numbers between 1 and N. As soon as we reach zero, we can stop multiplying and output L zeros. Otherwise we output the computed digits (for small factorials).

The more interesting problem is to find the first K digits. In the easy input you had to compute them for factorials of small numbers. It is possible to simply compute those factorials and output only their first K digits. You couldn't do that with the hard input. The factorials are simply too large.

We can write N! as 10log10(N!). We can write log10(N!) as I+F, where I is the integer part of log10(N!) and F is the fractional part of log10(N!). So N!=10(I+F)=10I*10F. Denote f(K,N) the first K digits of N and D the number of digits of N!. 10F is less than 10 so D=I+1. Then f(K,N)=floor(N!/10(D-K))=floor(10(I-D+K)*10F)=floor(10(K-1)*10F). The only problematic part is finding F.

We will compute log10(N!) and take only the fractional part. We can compute it as log10(N!)=log10(1)+log10(2)+...+log10(N) or use Stirling formula. The latter one is faster and gives accurate enough results for large numbers. You can find it at en.wikipedia.org/wiki/Stirling's_formula (a sketch of proof included).

You could use any library, which works with arbitrarily precise real arithmetics for example bc or BigDecimal in Java. A bc program solving both inputs is included.