### Factorial trailing digits题号：160 难度： 60 中英对照

For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,

9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664

Find f(1,000,000,000,000)

### Code

public final class p1602 {

public static void main(String[] args) {
long start=System.nanoTime();
long result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

public static long run() {
return factorialSuffix(1000000000000L);//1000000000000L
}

// The last 5 digits of n!, excluding trailing zeros.
private static long factorialSuffix(long n) {
long twos = countFactors(n, 2) - countFactors(n, 5);  // Always non-negative for every n
// We can reduce 'twos' because there is a cycle: 2^5 = 2^2505 = 32 mod 100000
if (twos >= 2505)
twos = (twos - 5) % 2500 + 5;
//step 1: get n! with out 2 and 5. Remember mod 100000
//step 2: get the remaining 2 that could not get zero
return factorialish(n) * powMod(2, (int)twos, 100000) % 100000;
}

//return x^y mod m.
public static int powMod(int x, int y, int m) {
if (x < 0)
throw new IllegalArgumentException("Negative base not supported");
if (y < 0)
throw new IllegalArgumentException("Modular reciprocal not supported");
if (m <= 0)
throw new IllegalArgumentException("Modulus must be positive");
if (m == 1)
return 0;

// Exponentiation by squaring
int z = 1;
while (y != 0) {
if ((y & 1) != 0)
z = (int)((long)z * x % m);
x = (int)((long)x * x % m);
y >>>= 1;
}
return z;
}

// Equal to n! but with all factors of 2 and 5 removed and then modulo 10^5.
// The identity factorialIsh(n) = oddFactorialish(n) * evenFactorialish(n) (mod 10^5) is true by definition.
private static long factorialish(long n) {
return evenFactorialish(n) * oddFactorialish(n) % 100000;
}

// The product of {all even numbers from 1 to n}, but with all factors of 2 and 5 removed and then modulo 10^5.
// For example, evenFactorialish(9) only considers the numbers {2, 4, 6, 8}. Divide each number by 2 to get {1, 2, 3, 4}. Thus evenFactorialish(9) = factorialish(4).
private static long evenFactorialish(long n) {
if (n == 0)
return 1;
else
return factorialish(n / 2);
}

// The product of {all odd numbers from 1 to n}, but with all factors of 2 and 5 removed and then modulo 10^5.
// By definition, oddFactorialish() never considers any number that has a factor of 2. The product of the numbers that not a multiple of 5 are accumulated by factorialCoprime().
// Those that are a multiple of 5 are handled recursively by oddFactorialish(), noting that they are still odd after dividing by 5.
private static long oddFactorialish(long n) {
if (n == 0)
return 1;
else
return oddFactorialish(n / 5) * factorialCoprime(n) % 100000;
}

// The product of {all numbers from 1 to n that are coprime with 10}, modulo 10^5.
// The input argument can be taken modulo 10^5 because factorialoid(10^5) = 1, and each block of 10^5 numbers behaves the same.
private static long factorialCoprime(long n) {
n %= 100000;
long product = 1;
for (int i = 1; i <= n; i++) {
if (i % 2 != 0 && i % 5 != 0)
product = i * product % 100000;
}
return product;
}

// Counts the number of factors of n in the set of integers {1, 2, ..., end}.
// For example, countFactors(25, 5) = 6 because {5, 10, 15, 20} each has one factor of 5, and 25 has two factors of 5.
private static long countFactors(long end, long n) {
if (end == 0)
return 0;
else
return end / n + countFactors(end / n, n);
}
}
16576
10ms