POJ 1150 The Last Non-zero Digit

Problem Description:
Given N, M, find the last non-zero digit in N! / (N - M)!.

Constraints:
0 ≤ M ≤ N ≤ 2e7

Solution:
We can find a and k such that in O(lg x) time, given that e is 2 or 5 (because they are prime, we can apply Wilson's theorem for the periodic part where (e - 1)! % e). With this, we can find by comparing and truncating k (truncating k = min(count_of_2, count_of_5) means we truncate all trailing zeros). We can get 2 linear congruence relations on mod 2 and mod 5, and with CRT we can retrieve that for mod 10, which is the desired value.

Code:

```#include <iostream>
#include <algorithm>

int F[2][5];

int N, M;

int mod_fact(int n, int p, int &e) {
e = 0;
if (n == 0) return 1;
int res = mod_fact(n / p, p, e);
e += n / p;
if (n / p & 1) return res * (p - F[p == 5][n % p]) % p;
return res * F[p == 5][n % p] % p;
}

int mod_inv(int v, int p) {
int r = 1;
for (int i = p - 2; i; i >>= 1) {
if (i & 1) r = r * v % p;
v = v * v % p;
}
return r;
}

int mod_pow(int v, int p, int m) {
int r = 1;
for (int i = p; i; i >>= 1) {
if (i & 1) r = r * v % m;
v = v * v % m;
}
return r;
}

signed main() {
for (int i = F[0][0] = 1; i < 2; ++i) F[0][i] = F[0][i - 1] * i % 2;
for (int i = F[1][0] = 1; i < 5; ++i) F[1][i] = F[1][i - 1] * i % 5;
std::ios::sync_with_stdio(false);
while (std::cin >> N >> M) {
int a[2][2], e[2][2];
a[0][0] = mod_fact(N, 2, e[0][0]);
a[0][1] = mod_fact(N, 5, e[0][1]);
a[1][0] = mod_fact(N - M, 2, e[1][0]);
a[1][1] = mod_fact(N - M, 5, e[1][1]);
e[0][0] -= e[1][0];
e[0][1] -= e[1][1];
int x = std::min(e[0][0], e[0][1]), m[2];
if (e[0][0] > x) m[0] = 0;
else m[0] = a[0][0] * mod_inv(a[1][0], 2) % 2;
if (e[0][1] > x) m[1] = 0;
else m[1] = a[0][1] * mod_inv(a[1][1], 5) * mod_inv(mod_pow(2, x, 5), 5) % 5;
for (int i = 0; i < 10; ++i) {
if (i % 2 == m[0] && i % 5 == m[1]) {
std::cout << i << std::endl;
}
}
}
return 0;
}
```