- Correct output – D1
- Correct output – D2
- C program solving the easy data set
- Less efficient program solving the difficult data set
- More efficient program solving the difficult data set

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**!=2^{i} *
3^{j} * 5^{k} * 7^{l} * ... 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**! / (2^{k} * 5^{k}). Therefore we can compute
the result using the equation:

(**N**! / (2^{k} * 5^{k})) mod 10 =
((**N**! / (2^{i} * 5^{k})) mod 10 * 2^{i-k}
mod 10) mod 10

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
2^{a} * 5^{b} where a and b are the highest numbers such
that the i is divisible by this product.
Number (**N**! / (2^{i} * 5^{k})) 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 (2^{i-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
2^{i-k} mod 10. Observe, that

2^{1} mod 10 = 2,
2^{2} mod 10 = 4,
2^{3} mod 10 = 8,
2^{4} mod 10 = 6,
2^{5} mod 10 = 2,
2^{6} mod 10 = 4,
...

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 2^{i-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 3^{a} mod 10,
7^{b} mod 10, 9^{c} mod 10 in the similar way as we did for
2^{i-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**(**N**^{2}) 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**=2^{a} * 5^{b}). 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.