[BOJ]1676번: 팩토리얼 0의 개수

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

 

java 소스

import java.io.*;
 
public class Main {
    public static void main(String[] args) {
        try {
        
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
            int num = Integer.parseInt(br.readLine());
            int result = 0;
            
            for (int i = 5; i <= num; i *= 5) {
                result += num / i;
            }
            
            System.out.println(result);
            
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}
 
 

 

c++소스

#include <iostream>
 
using namespace std;
 
int main()
{
    int n;
    cin >> n;
 
    // 10 = 2 * 5 인데, 
    // 2의 배수보다 5의 배수가 더 적으므로
    // 인수 중 5의 개수만 세면 된다.
    int cnt_5 = 0;
    for (int i = 5; n / i >= 1; i *= 5)
    {
        cnt_5 += n / i;
    }
    cout << cnt_5;
 
    return 0;
}

 

 

TIP

10은 2 * 5이지만, N!에서 2의 개수가 항상 5의 개수보다 같거나 많을 것이다.

그러니 5의 개수만을 구하면 된다. 

 

이 때, 5의 n승의 개수를 고려해주어야 한다. 

에라토스테네스의 체를 이용해 생각한다면 5의 n승의 배수는 5를 n개 만큼 포함하고 있다.

 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

 

 

따라서 수를 5로 나누어 떨어지는 몫의 수를 모두 더하면, N!에 포함되는 5의 개수를 구할 수 있다.