[종만북] 문제: PASS486

문제

$[lo, hi]$까지의 범위에 속하는 약수의 개수가 $n$개인 정수의 개수를 구하는 문제입니다.

범위: $1 \leq lo \leq hi \leq 10,000,000, hi - lo \geq 1,000,000$

문제 링크

---

서론

에라토스테네스의 체 를 이용하여 소수들을 대량으로 빠르고 정확하게 구합시다.

에라토스테네스의 체

설명은 위키백과를 인용하겠습니다.

---

알고리즘 구상

무식하게 풀어보기

어떤 정수의 약수가 몇개인지 파악하는 알고리즘을 구하는 건 $O(\sqrt {n})$이 걸립니다.

이를 $[lo, hi]$의 범위 내에 존재하는 모든 정수에 대해 알고리즘을 실행시키면, 프로그램이 시간 안에 동작할 수 없습니다.

약수 개수 구하기

일단 약수의 개수부터 구하는 알고리즘을 생각해봅시다.

사실 $i(2 \leq i \leq k)$의 수에 대해 $k \bmod i$를 수행하면 됩니다. $O(n)$알고리즘이죠.

사실, $k = a \times b$형태로 나타낼 수 있어서, $a$가 약수라면, $b$도 약수가 됩니다.

따라서 $b = \frac{k}{a}$로 나타낼 수 있기에, 약수를 한번에 두 번 셀 수 있습니다.

대신 $k = \sqrt{a} \times \sqrt{a}$형태로 존재할 수 있는 $a$가 존재하면 한 번만 세야 합니다. 이 알고리즘은 $O(\sqrt{n})$시간에 동작합니다.

이 방식으론 한계가 있기 때문에, 다른 방식으로 알고리즘을 설계하려고 합니다.

$k = a \times b$형태에 주목해봅시다. 우리는 어떤 정수가 주어지면 이를 소인수분해 형태로 표현할 수 있습니다.

$k = 2^x \times 3^y$이런 식으로 표현할 수 있습니다, 이때 약수의 개수는 $(x+1)(y+1)$입니다. 일반화하면, (소인수 분해해서 나온 소수의 제곱 + 1)을 곱한 것이라고 볼 수 있겠습니다.

약수의 개수를 세는 알고리즘은 $factors(n)$이라고 가정하겠습니다.

$n = \prod_{i} p_i^{a_i}$

$factors(n) = factors(\prod_{i} p_i^{a_i}) = \prod_{i} (a_i+1)$로 정의 가능합니다.

점화식 이용

더 나아가서, 이런 점화식을 설계할 수 있습니다.

$21$이라는 수는 $3$과 $7$로 나뉩니다. 약수의 개수는 총 4개입니다.

우리는 $21$이라는 수를 통해 $63$의 약수의 개수가 몇 개인지를 파악하고 싶습니다.

이전에 $2 \times 2$였으나, $21$에 $3$이 추가로 곱해져서 $(2+1) \times 2$가 되었죠.

따라서 $factors(63) = factors(\frac{63}{3}) \times \frac{2+1}{2}$,

$factors(k) = factors(\frac{k}{p}) \times \frac{a+1}{a}$, $p$는 $k$의 가장 작은 소인수, $a$는 $p^a$가 $k$를 나눌 수 있는 최대 지수를 의미합니다.

알고리즘 설계

1. 에라토스테네스의 체를 이용해 $1$부터 $10000000$까지 가장 작은 소인수 값을 뜻하는 minFactor[]를 정의합니다.
2. minFactor[i]가 $k$에서 몇 번 쓰이는지 계산하고, 그 값을 minFactorPower[i]에 저장합니다.
3. 앞서 구한 점화식을 이용해 정수 $k$가 몇 개의 약수를 가지는지 계산합니다.
4. 범위 $[lo, hi]$까지 반복문을 통해 조건을 만족하는 정수의 개수를 파악합니다.

---

알고리즘 구현

init()

알고리즘 1 ~ 3단계까지의 과정을 이행합니다. 에라토스테네스의 체를 이용합니다.

void init() {
    // 에라토스테네스의 체를 이용해 정수 k의 최소 소인수를 구한다.
    minFactor[0] = minFactor[1] = -1; // 존재하지 않음
    for (int i = 2; i <= MAX; i++) {
        minFactor[i] = i; // 소수임을 의미한다.
    }
    int sqrtMAX = sqrt(MAX);
    for (int i = 2; i <= sqrtMAX; i++) {
        if (minFactor[i] == i) {
            for (int j = i * i; j <= MAX; j += i) {
                if (minFactor[j] == j) minFactor[j] = i;
            }
        }
    }

    // 앞서 구한 minFactor[]를 이용해 factors를 구한다.
    factors[1] = 1;
    for (int i = 2; i <= MAX; i++) {
        if (minFactor[i] == i) {
            minFactorPower[i] = 1;
            factors[i] = 2; // 소수임을 의미함.
        } else {
            int m = i / minFactor[i];
            if (minFactor[i] != minFactor[m]) {
                minFactorPower[i] = 1; // 이제 이 소인수를 더 이상 쓸 수 없음.
            } else {
                minFactorPower[i] = minFactorPower[m] + 1;
            }
            int a = minFactorPower[i];
            factors[i] = (factors[m] / a) * (a + 1);
        }
    }
}

answer()

앞서 구한 factor[]를 이용해 조건에 부합하는 정수의 개수를 구합니다.

int answer() {
    int count = 0;
    for (int i = lo; i <= hi; i++) {
        if (factors[i] == n) count++;
    }
    return count;
}

최종 코드

여기에서 확인하세요!