Funcia
Lv.1mathnumber-theorysieve

약수의 개수 구하기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

양의 정수 배열 nums가 주어집니다. 각 nums[i]의 약수의 개수를 구해 같은 순서로 배열에 담아 반환하세요.

약수는 나누어떨어지게 하는 양의 정수입니다. 예를 들어 12의 약수는 1, 2, 3, 4, 6, 12로 6개입니다.

입출력 예

numsresult
[1, 6, 12][1, 4, 6]
[7, 36, 100][2, 9, 9]
[5000000][56]

입출력 예 설명

예 1 — 1의 약수는 1 하나, 6의 약수는 1, 2, 3, 6입니다.

예 2 — 7은 소수이므로 약수가 2개입니다. 36=22⋅3236 = 2^2 \cdot 3^2, 100=22⋅52100 = 2^2 \cdot 5^2는 모두 약수가 3×3=93 \times 3 = 9개입니다.

예 3 — 5,000,000=26⋅575{,}000{,}000 = 2^6 \cdot 5^7이므로 약수는 7×8=567 \times 8 = 56개입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(nums: int[]) → int[]

제한 사항

  • 1≤1 \le nums.length ≤200,000\le 200{,}000
  • 1≤1 \le nums[i] ≤5,000,000\le 5{,}000{,}000

기대 복잡도

시간
O(M log log M + Q log M)
공간
O(M)

입출력 예

nums기대 출력
[1,6,12][1,4,6]
[7,36,100][2,9,9]
[5000000][56]

힌트

힌트

x=p1e1p2e2⋯pkekx = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}로 소인수분해되면 약수의 개수는 (e1+1)(e2+1)⋯(ek+1)(e_1 + 1)(e_2 + 1) \cdots (e_k + 1)입니다. 각 소인수를 0번부터 eie_i번까지 고를 수 있기 때문입니다.

값이 많으므로 소인수분해를 빠르게 해야 합니다. 에라토스테네스의 체를 변형해 각 수의 가장 작은 소인수(spf[x])를 미리 구해 두세요. 그러면 x를 spf[x]로 계속 나누는 것만으로 소인수분해가 되고, 나누는 횟수는 log⁡2x\log_2 x 이하입니다.

복잡도 목표

값마다 x\sqrt{x}까지 나눠 보면 값 하나에 2천 번이 넘어, 20만 개에서는 효율성 테스트에서 시간 초과가 납니다. 체를 한 번 만드는 O(Mlog⁡log⁡M)O(M \log \log M)과 값마다 O(log⁡M)O(\log M)이 필요합니다(MM은 최댓값).

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)248 ms추정
C++ (GCC, gnu++23)248 ms도출됨
Python 3.131000 ms도출됨
Java 251490 ms도출됨
Kotlin 2.4 (JVM)1496 ms추정
C# 14 (.NET 10)1496 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance603판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.