백준 2004 - 조합 0의 개수

문제 설명

 

 

 

=> 어떠한 수의 0의 갯수를 세기 위해서는 소인수 분해를 한 후에 2와 5의 갯수를 센후 적은 수를 구하면 된다. 

=> 이번 입력 값은 20억개이므로 브루트포스로 2와 5의 갯수를 세어보면 TLE가 발생한다. 

=>그러한 문제를 해결하기 위해 다음과 같은 방법을 사용한다. 

 

for( long i=5; i<=number; i*=5)
    {
        cnt+=number/i;
    }

=>이와 같은 방법을 사용할 경우 시간 단축의 효과가 있다. 

=> 본인은 이 방법을 깨닫기까지 오랜 시간이 걸렸다. 

=> 입력값이 20억까지 갈 수 있으므로 자료형을 주의하여 써야한다. 

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

long CountFive(long number)
{
    long cnt=0;
    for( long i=5; i<=number; i*=5)
    {
        cnt+=number/i;
    }
    return cnt;
}

long CountTwo( long number)
{
    long cnt=0;
    for( long i=2; i <=number; i*=2)
    {
        cnt+=number/i;
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    long long N, M;
    cin >> N >> M;
    
    long five = CountFive(N);
    five-=CountFive(M);
    five-=CountFive(N-M);
    
    long two = CountTwo(N);
    two-=CountTwo(M);
    two-=CountTwo(N-M);
    
    cout<<min(five, two)<<'\n';
    
    return 0;
}