[백준2004] 조합 0의 개수

2004. 조합 0의 개수

Idea

0의 개수를 찾기 위해서는 최종값을 소인수분해 했을때 소인수 2의 개수와 5의 개수를 구해야 한다.

즉 nCm의 소인수분해를 해야한다. 하지만 소인수 분해를 위해 1부터 n까지 완전 탐색을 하면 O(n)의 시간복잡도가 필요하여 시간초과가 일어난다. (n<=20억)

 

n!에서 인수 p의 개수를 구한다고 생각해보자.

모든 p의 배수는 인수를 p를 적어도 1개 가지므로 1번 카운트한다. p^2의 배수는 인수 p를 적어도 2개를 가지므로 2번 카운트한다. 이때 중요한것이 모든 p^2의 배수는 p의 배수라는 것이다. 즉, 모든 p^2의 배수는 이미 p의 배수를 카운트하는 과정에서 1번 카운트 되었다. 이때 p^2은 인수 p가 2개이므로 2번 카운트 해야하는데 이때 이미 1번 이전과정에서 카운트 되었으므로 1번만 카운트 하면된다.

 

일반화 해보면,

모든 k에 대해 p^k의 배수는 k번 카운트해야하지만 이미 p^k-1의 배수를 카운트하는 과정에서 k-1번 카운트되었으므로 1번만 카운트하면 된다. 즉, p^1부터 p^k까지 순차적으로 배수를 찾으면서 각각 1번씩만 카운트하면 되는것이다.

 

코드로보면 아래와 같다.

ll numPFactor(ll p, ll x) {
    
    ll ret = 0;
    ll idx = p; 
    while (idx <= x) {
        ret += x / idx;
        idx *= p;
    }
    
    return ret;
}

다음은 x!을 소인수분해 했을때 인수 p의 개수를 구하는 함수이다.

idx는 p^k로 k는 1부터 x^k가 x보다 작거나 같을때까지 순차적으로 증가한다. 이때 배수의 개수는 x에서 idx(p^k)를 나눔으로써 구한다.

 

nCm = n!/(n-m)!m! 이므로 n!에서의 2,5 소인수의 개수에서 (n-m)!, m!에서의 2,5 소인수의 개수를 빼주면 된다. 그후 0의 개수란 10인수의 개수를 구하는 것이므로 2,5 소인수중 더 적은 개수를 출력한다.

Solution

#include <iostream>
#include <cmath>

using namespace std;

using ll = long long;

ll numPFactor(ll p, ll x) {
    
    ll ret = 0;
    ll idx = p; 
    while (idx <= x) {
        ret += x / idx;
        idx *= p;
    }
    
    return ret;
}
int main() {
    ll n, m;
    cin >> n >> m;
    
    ll num2 = numPFactor(2,n) - numPFactor(2,n-m) - numPFactor(2,m);
    ll num5 = numPFactor(5,n) - numPFactor(5,n-m) - numPFactor(5,m);
    
    int ret = (num2 < num5) ? num2 : num5;
    cout << ret;
}