팩토리얼 0의 개수 구하기

팩토리얼이란 계승을 의미한다

예를들어 10의 팩토리얼은 1 * 2 * 3 * 4 * 5* 6 * 7 * 8 * 9 * 10 을 의미한다. 현재 구하고 싶은 값은 10 팩토리얼에서 나오는 연속된 0의 갯수이다. 예를들어 10팩토리얼의 값 3628800 이있다면 여기서 가장 뒤의 연속된 0 의 개수를 구하는 것이다.

뒤 자리가 0이 나오기 위해서는 값에 10이 더해지는 수 밖에 없다. 따라서 2 * 5 가 몇번나왔는지만 확인하면 된다.

해결을 하기 위해서는 2가지 방법이 있다.

1. 3628800 을 소인수 분해 하여 총 5가 몇개나오는지 확인하는 방법이 있다.

2. 10의 값을 5로 나누고 몫의 값을 파악하는 방법 + 25 * 1, 25 * 2 와 같이 5 * 5 가 두번 나올 경우를 파악

// HelloNew_C+.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.
//

#include "stdafx.h"
#include<iostream>
#include<stdio.h>
#include<string>
#include<stdio.h>
#include<stdbool.h>
#include<stack>

using namespace std;

int main(){
	
	int n;
	int res = 0;
	cin >> n;

	// 5의 개수 만큼 cnt
	for (int i = 5; i <= n; i = i * 5){
		res = res + (n / i);
	}
	cout << res << endl;

}

위의 해당 구문이 실행 되면 다음과 같이 동작한다.

i = 5

res = res + ( 100 / 5 )  

res 에는 20이 담긴다. 그 뒤 5 * 5 와 같이 5가 두번 들어가는 5 의 2 승의 값을 n 으로 나눔으로써 5가 2번들어가는 경우의 수를 구한다.

 

i = i * 5 => ( 25 )

res = 20 + ( 100 / (5 * 5) )

res = 24