Funcia
Lv.1mathnumber-theorysieve

Divisor Counts

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Given an array nums of positive integers, return the number of divisors of each nums[i], in the same order. For example, 12 has the 6 divisors 1, 2, 3, 4, 6 and 12.

Examples

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

Example 3 — 5,000,000=26⋅575{,}000{,}000 = 2^6 \cdot 5^7 has 7×8=567 \times 8 = 56 divisors.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

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

Constraints

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

Expected complexity

Time
O(M log log M + Q log M)
Space
O(M)

Examples

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

Hint

Hint

If x=p1e1⋯pkekx = p_1^{e_1} \cdots p_k^{e_k}, it has (e1+1)⋯(ek+1)(e_1 + 1) \cdots (e_k + 1) divisors. Precompute the smallest prime factor spf[x] of every number up to the maximum with a sieve; then dividing by spf[x] repeatedly factors x in at most log⁡2x\log_2 x steps. Trial division up to x\sqrt{x} for each of 200,000 values exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)248 msestimated
C++ (GCC, gnu++23)248 msderived
Python 3.131000 msderived
Java 251490 msderived
Kotlin 2.4 (JVM)1496 msestimated
C# 14 (.NET 10)1496 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4010verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.