当前位置:首页 » Project Euler » 详细页

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)

Solution

不可能直接算一万亿的阶乘,时间消耗太大。题目要求得到阶乘结果去除末尾0后的最后5位,总体上分两步,第一步是去除末尾0,第二步是得到后五位,即模100000。 1. 去除末尾0 。 我们知道,只要存在因子2和因子5,阶乘末尾就会出现0。所以要在算阶乘的过程去除因子2和5。但是要注意到,一万亿的因子2的个数肯定比因子5的个数多,没有因子5,因子2不会产生0的结果。因此,在去除2和5后,要乘以比因子5多的那部分因子2。 - 去除因子2和5。 10^12的阶乘可以通过奇数阶乘和偶数阶乘计算得到。 - 乘以多的因子2。 计算出因子2的个数和因子5的个数,然后相减就可以得到多余的因子2的个数。 2. 模100000 。 阶乘的结果要模10000,整个计算过程记住就好。

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