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; }