백준 2004 조합 0의 개수

nCm의 끝자리 개수를 구하는 문제.

 

나는 n!, m!, (n-m)!의 10의 자리 수를 각각 구해서 뺴주려고 했다.

그러나 long long의 범위에서 n!의 값을 구할수 없다는 것을 간과했다....

 

n!을 구하고, 2와 5의 개수를 구해서 10의 개수를 구하면 안된다!

 

static long cnttwo(long a) {
		long count = 0;
		
		for(long i = 2; i<=a; i*=2) {
			count+=a/i;
		}
		return count;
	}

 

이런 식으로 팩토리얼을 직접 구하지 않고 2와 5의 개수를 구할수 있다.

5! = 5 * 4 * 3 * 2 * 1 이라고 했을떄,

2의 배수를 저렇게 뽑아내는 식..