For this problem we provide output files for both data sets as well as three programs. The first program is very simple but also very inefficient and can be used to solve only easy data set. The second program runs in time O(N 3) where N is number of digits of a input number. Since the difficult input data set contained numbers with N=91 digits, it is possible to use this program for solving it. There is still another, more efficient program working in time O(N 2), which we present as well.
Consider the number N! factored into product of powers of prime numbers. It means N!=2i * 3j * 5k * 7l * ... Note, that for each N>1 the power i is greater than k. It means, that the last non-zero digit of N! is the same as the last digit of N! / (2k * 5k). Therefore we can compute the result using the equation:
Number i can be obtained easily - we will divide each a=1,2,...,N by 2 until the resulting number is not divisible by 2 and after each division we will add one to the variable i. Number k can be obtained in the same manner. Let f(i) denotes the number which we obtain by dividing i by the 2a * 5b where a and b are the highest numbers such that the i is divisible by this product. Number (N! / (2i * 5k)) mod 10 is equal to f(N!) mod 10 and can be computed as f(1) * f(2) * ... * f(N) mod 10. We will perform operation mod 10 after each multiplication in order to keep the resulting number as small as possible.
The advantege of this approach is that we do not need to implement arithmetics of large numbers. Some ideas used here are used in the second, more efficient program, as well.
The second program also computes the result as (2i-k mod 10 * f(N!) ) mod 10. Numbers i and k are computed much more efficiently. More precisely
(We get zero after finite number of divisions.) Number k can be computed in the same way. After that we can compute i-k and we need to find 2i-k mod 10. Observe, that
i.e. the period is 4 and we need only to compute (i-k) mod 4 and then to find corresponding last digit. This observation can help us to simplify computation of i and k - we do not need their exact values (that can be long) but we need only (i-k) mod 4.
We have shown how to compute 2i-k mod 10. Now let us consider f(N!) mod 10 = ((f(1) mod 10) * (f(2) mod 10) * ... * (f(N) mod 10)) mod 10. Note, that f(i) mod 10 is always 1,3,7 or 9. If we knew, how many 3,7,9 are among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10), we could compute 3a mod 10, 7b mod 10, 9c mod 10 in the similar way as we did for 2i-k (last digits of powers of 3,7,9 are also periodical).
To compute the number of 3,7,9 among (f(1) mod 10), (f(2) mod 10), ..., (f(N) mod 10) is not so easy. We will divide numbers 1,2,...,N into groups so, that in each group are numbers with same quotient i/f(i) and we will compute number of 3,7,9 among (f(i) mod 10) for each such group separatelly (there are O(N2) such groups). First, let us consider a group in which i/f(i)=1. This is the group of all numbers not divisible by 2 and 5. The number of 3,7,9 in this group is the same as number of 3,7,9 among 1 mod 10, 2 mod 10, ..., N mod 10. This number can be counted easily - it is N div 10 + a where a is 1 if the last digit of N is at least 3 (resp. at least 7 or at least 9). Now let us consider a group in which i/f(i)=L (where L=2a * 5b). We obtain this group by taking each L-th number from the sequence 1,2,3,... and dividing it by L. It means that number of 3,7,9 for this group will be the same as the number of 3,7,9 among 1 mod 10, 2 mod 10, ..., (N div L) mod 10.
Now we know everything we needed for construction of a program. Since numbers in the input file are long, we need to implement arithmetics for long numbers. However, by careful implementation we can achieve that only division of a long number by small integer is necessary.
Description of the algorithm used in this program will be available later.