28437번 - 막대 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1260 | 580 | 461 | 48.171% |
문제
길고 얇은 막대를 만드는 과정은 다음과 같습니다.
- 기본으로 사용할 막대를 고릅니다. 사용 가능한 막대의 길이는 $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$을 넘지 않음을 증명할 수 있습니다.
예제 입력 1
5 1 2 3 4 5 6 1 2 3 4 5 6
예제 출력 1
1 2 2 4 2 5
길이 $6$인 막대를 만드는 서로 다른 방법은 다음과 같습니다.
- 길이가 $1$인 막대를 고릅니다. 길이를 $2$배 늘려 길이를 $2$로 만듭니다. 길이를 $3$배 늘려 길이를 $6$으로 만듭니다.
- 길이가 $1$인 막대를 고릅니다. 길이를 $3$배 늘려 길이를 $3$로 만듭니다. 길이를 $2$배 늘려 길이를 $6$으로 만듭니다.
- 길이가 $1$인 막대를 고릅니다. 길이를 $6$배 늘려 길이를 $6$으로 만듭니다.
- 길이가 $2$인 막대를 고릅니다. 길이를 $3$배 늘려 길이를 $6$으로 만듭니다.
- 길이가 $3$인 막대를 고릅니다. 길이를 $2$배 늘려 길이를 $6$으로 만듭니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호