gokuu007's blog

Combinatorics — Factor's
By gokuu007, history, 21 month(s) 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 (11)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) 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
»
21 month(s) 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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gokuu007 (previous revision, new revision, compare).

→ Reply