0w1

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 { \displaystyle x! = a * e^k, e \nmid a } 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 { \displaystyle N! / (N - M)! } 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;
}