11687 팩토리얼 0의 개수

www.acmicpc.net/problem/11687

11687번: 팩토리얼 0의 개수

<아이디어>

N!에서 가장 끝 0의 개수를 세려면 2 * 5의 수를 세면 된다.

 

N!을 소인수분해 했을 때, 2의 개수와 5의 개수를 생각한다면

min(2의 개수, 5의 개수) 가 M인 N! 중 N의 최소값을 찾으면 된다.

 

2의 개수는 N이 짝수일 때마다 1개 이상 생기고, 5의 개수는 N이 5의 배수일 때마다 1개 이상 생기므로 2의 개수는 항상 5의 개수보다 크거나 같다. 그러므로 5의 개수만 신경쓰자.

 

그러면 N!에서 5의 개수는 몇개일까?

 

5의 배수의 개수 + 25의 배수의 개수 + 125의 배수의 개수 + 625의 배수의 개수.... 가 된다.

 

예를 들어, N을 30이라고 하자. N!에 5의 개수는 몇개일까?

 

5, 10, 15, 20, 25, 30 총 6개일까? 아니다.

25는 5의 제곱이므로 2개가 들어간다. 그래서 30!에 5의 개수는 총 7개이다.

 

M의 범위가 100,000,000 이기 때문에 이를 paraparametric search로 찾아준다.

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
lld count_5(lld mid)
{
    lld tmp = mid, cnt = 0;
    while(tmp>=5)
    {
        tmp /= 5;
        cnt += tmp;
    }
    return cnt;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    lld m;
    cin>>m;
 
    lld l = 5, r = 5e9+1;
    while(l<r)
    {
        lld mid = (l+r)/2, cnt = count_5(mid);
        if(cnt<m) l = mid+1;
        else r = mid;
    }
 
    if(m==count_5(r)) cout<<r;
    else cout<<-1;
 
    return 0;
}