gokuu007's blog

Combinatorics — Factor's
By gokuu007, history, 17 months ago, In English

************************************ Factors ***************************************

gokuu007

So recently when I was studying some basics of combinatorics I got an idea of a problem, So in this blog I will be sharing the problem and the solution of the problem. And the solution of the problem.

So the problem statement is :

You are given a no N and m queries. there 3 type of queries :

Type 1 : You have to print the total no of factors of N. (1<=N<=10^18)

Type 2 : You have to print the total sum of factors of N.

Type 3 : You have to print the total sum of the reciprocals of the factors of N.

Solution :

Can any one come up with a better solution ??

  • Vote: I like it
  • -17
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

1<=N<=10^18 Time Complexity O(log(N)). Space Complexity O(N).

Is this a joke?

→ Reply
»
17 months ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

1) Time complexity is never less than space complexity
2) You will be showered in money if you solve factorization in O(log n) (iirc sum of divisors and prime factorization are back and forth problems)

→ Reply