[알고스팟] PASS486 - 비밀번호 486 (C++, 에라토스테네스의 체)

문제

https://algospot.com/judge/problem/read/PASS486

algospot.com :: PASS486

 

 

풀이

 

종만북 난이도: 중

 

에라토스테네스의 체를 활용한 소인수 분해를 이용해야해서 어려웠던 문제이다.

특히 소인수 분해까지는 구현해도 수학적인 최적화를 진행하지 않으면 제 한 시간 안에 맞출 수 없다.

 

해당 문제에서 사용되는 에라토스테네스의 체와 소인수 분해는 아래 링크에서 확인하자.

에라토스테네스의 체와 소인수 분해

 

어떤 수n의 약수의 개수를 알기 위한 가장 쉬운 방법은 n이하의 수를 처음부터 끝까지 모두 나눠보고 나누어 떨어지는지 확인하는 것이다. 물론 문제에서 주어지는 n의 최댓값은 10,000,000이기 때문에 너무나 오래 걸린다.

 

따라서 소인수 분해를 이용하여 더 빠르게 약수의 개수를 구하는 방법을 사용하자.

84의 약수는 1, 2, 3, 4, 6, 7, 12, 14, 24, 42, 84로 총 12개이다.

84는 소인수 분해시 2^2 x 3 x 7로 나타낼 수 있는데, 각 소수의 등장 개수에 주목하자.

 

각 약수는 모두 소인수의 등장 개수로 나타낼 수 있다.

1 = 2^0 x 3^0 x 7^0

2 = 2^1 x 3^0 x 7^0

3 = 2^0 x 3^1 x 7^0

4 = 2^2 x 3^0 x 7^0

6 = 2^1 x 3^1 x 7^0

7 = 2^0 x 3^0 x 7^1

.

.

.

42 = 2^1 x 3^1 x 7^1

82 =  2^2 x 3^1 x 7^1

 

즉, (각 소인수의 등장 횟수+1)를 모두 곱해준 것이 약수의 개수가 된다.

따라서 84의 약수는 3 x 2 x 2 =12이다.

 

하지만 위의 소인수 분해 알고리즘으로 각 수를 소인수 분해하고 등장 횟수를 곱해 약수의 개수를 구해내면 시간 초과가 발생한다.

따라서 모든 수를 소인수 분해하지 않아도 되는 풀이를 살펴보자.

 

84의 2배인 168은 2^3 x 3 x 7 으로 나타낼 수 있다.

약수의 개수는 2의 등장횟수 +1 인 3을 4로 교체하면, 12*(4/3)로 나타낼 수 있다.

즉, n의 약수의 개수(divisor_cnt[n])를 구하기 위해서는 n의 가장 작은 소인수(p)와 그 등장 횟수(a)라고 할 때,

divisor_cnt[n] = divisor_cnt[n/p] * ((a+1)/a) 라고 나타낼 수 있다.

 

이를 구현하기 위해 min_factor_pow[n]에 n의 가장 작은 소인수(min_factor[n])의 등장 횟수를 저장해 두자.

 

1. n이 소수라면

 약수의 개수는 2이다.

 

2. n이 소수가 아니라면

n의 가장 작은 소인수(p = min_factor[n])로 나눈 수 n/p의 min_factor[n/p]가 p와 같은 지 확인해야 한다.

만약 min_factor[n/p]가 p와 다르다면 min_factor_pow[n]은 그대로 1이 되고

p와 같다면 min_factor_pow[n] = min_factor_pow[n.p] +1 가 된다.

 

이를 구현한  CalcDivisorNum 함수를 확인해보자.

 

void CalcDivisorNum(){
  divisor_cnt[1] =1;
 
  for(int i=2; i<=MAX_NUM ; ++i){
    if(min_factor[i] == i){ //소수인 경우
      min_factor_pow[i] = 1;
      divisor_cnt[i] =2;
    }else{
      int p =min_factor[i];
      int m = i / p;
      if(p != min_factor[m])
        min_factor_pow[i] = 1;
      else
        min_factor_pow[i] = min_factor_pow[m] +1;
      int a =min_factor_pow[i];
      divisor_cnt[i] = (divisor_cnt[m]/a)*(a+1);
    }
  }
}

 

종만북을 보며 공부하고 있지만 아무리 꾸준히 해도 이런 수준의 최적화를 과연 직접 떠올릴 수 있을지는 의문이다...

 

코드