Please read the new rule regarding the restriction on the use of AI tools. ×

kobietvietcode's blog

how do you find sum of divisors?
By kobietvietcode, history, 2 hours ago, In English

i am looking for a O(n^(1/3)) solution because the numbers can get up to 1e18

can anyone please help me?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
82 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

Lets divide the task into parts :-

First finding prime factorization of the number in O(n^(1/3)):-

there is a CF blog on that already Link (Refer to that)

Second find sum of divisors from prime facorizaton :-

which is very standard thing (cp-algo)

$$$ \sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1} $$$

where p_i is the prime number and e_i is its frequency

→ Reply
  • »
    »
    20 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A little more explanation:

    $$$x^0 + x^1 + \cdots + x^n = \frac{x^{n+1}}{x - 1}$$$
    → Reply