[28437] 막대 만들기

문제 링크 : https://www.acmicpc.net/problem/28437

28437 - 막대 만들기

본문

길고 얇은 막대를 만드는 과정은 다음과 같습니다.

• 기본으로 사용할 막대를 고릅니다. 사용 가능한 막대의 길이는 $A_1, \cdots, A_N$입니다.
• 원하는 길이가 될 때까지 $0$번 이상 막대를 늘립니다. 기계에 $2$ 이상의 양의 정수 $k$를 설정해서 막대를 넣으면, 길이가 $x$였던 막대가 길이 $kx$의 막대가 됩니다.

주어진 $Q$개의 길이 각각에 대해 길이가 $L_i$인 막대를 만드는 방법의 수를 출력하세요. 두 방법이 서로 다르다는 것은 처음 선택한 막대가 다르거나, 막대를 늘리는 과정에서 입력한 정수 $k$의 수열이 서로 다르다는 것을 의미합니다.

입력

첫 줄에 막대의 개수 $N$이 주어집니다. $(1 \le N \le 100\,000)$ 

둘째 줄에 $N$개의 서로 다른 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어집니다. $(1 \le A_i \le 100\,000)$ 

셋째 줄에 만들고자 하는 막대 길이의 개수 $Q$가 주어집니다. $(1 \le Q \le 100\,000)$ 

넷째 줄에 $Q$개의 정수 $L_1, \cdots, L_Q$가 공백으로 구분되어 주어집니다. $(1 \le L_i \le 100\,000)$ 

출력

첫 줄에 $Q$개의 수를 공백으로 구분해 출력합니다. $i$번째 수는 길이가 $L_i$인 막대를 만드는 방법의 수입니다. 가능한 모든 입력에 대해 답이 $10^9$을 넘지 않음을 증명할 수 있습니다.

제한

시간 제한	메모리 제한
1sec	1024MB

---

풀이

문제의 이해부터 해보자. 어떤 막대 $x$를 만들기 위해서는, 현재 가지고 있는 막대 $a$를 이용하여, 그를 정수배하여 길이를 맞춰야 한다. 즉 $a$가 $x$의 약수여야만 가능하다. $a$를 $x$로 만들기 위해서는 $a$를 $x / a$배만큼 해야하고, 그 방법은 $x / a$의 1을 제외한 약수의 개수만큼 존재한다. 즉, 특정 수의 약수의 개수를 빠르게 구해야 하는 문제이다.

어떤 수의 약수를 구하기 위해서는 일반적으로 $O(\sqrt{N})$의 시간복잡도 방법을 사용한다. 다만 우리는 모든 막대에 대해, 모든 길이에 대한 수의 약수를 계산해야하므로, 이것은 1초 안에 동작할 수 없다. 약수를 구하는 또 다른 방법을 생각해야한다.

여기서 사용할 수 있는 방법이 dp이다. 막대의 길이가 최대 $100\,000$까지로 제한되어있으므로, $1$부터 $100\,000$까지의 약수를 모두 계산해놓으면 된다. 그 때 이전의 결과를 이용하기 위한 dp를 추가하는 것이다.

점화식으로는 top-down이 아닌 bottom-up을 사용해야 시간초과를 면할 수 있었다. dp[i x k] += dp[i] 점화식을 이용하였다. 이 점화식을 이용하면 전체 수행식이 $N/1 + N/2 + N/3 + \cdots N/N = O(N \log{N})$이 된다고 한다. N이 10만이므로 아슬아슬하게 시간제한에 들어갈 정도이다.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 8 / 7

#include <stdio.h>

#define MAX_IDX (100000 + 1)

int n, q;
int ans[MAX_IDX];

void solve() {
    for (int i = 1; i < MAX_IDX; ++i) {
        for (int j = i * 2; j < MAX_IDX; j += i) {
            ans[j] += ans[i];
        }
    }
    return;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        int a;
        scanf("%d", &a);
        ans[a] = 1;
    }

    solve();

    scanf("%d", &q);
    while (q--) {
        int l;
        scanf("%d", &l);
        printf("%d ", ans[l]);
    }

    return 0;
}