2004번 백준(Baekjoon)

<문제 풀이>

n과 m이 20억까지의 수를 가지고 있어서 O(N)만으로도 시간초과가 날 수 밖에 없다.

따라서 수학적인 방법으로 해결하여야 한다.

끝의 0의 개수를 세기 위해 1과 10을 제외한 10의 약수인 

5의 개수와 2의 개수를 세어 둘 중 작은 수를 가진 것이 끝의 0의 자리 숫자가 된다.

<정답 코드>

#include <iostream>
 
using namespace std;
 
int n, m;
int cnt5, cnt2;
 
int main()
{
    cin >> n >> m;
 
    for (long long i = 5; i <= n; i *= 5)
        cnt5 += n / i;
    for (long long i = 5; i <= n - m; i *= 5)
        cnt5 -= (n - m) / i;
    for (long long i = 5; i <= m; i *= 5)
        cnt5 -= m / i;
    for (long long i = 2; i <= n; i *= 2)
        cnt2 += n / i;
    for (long long i = 2; i <= n - m; i *= 2)
        cnt2 -= (n - m) / i;
    for (long long i = 2; i <= m; i *= 2)
        cnt2 -= m / i;
 
    if (cnt5 >= cnt2)
        cout << cnt2;
    else
        cout << cnt5;
 
    return 0;
}