Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

SPyofgame's blog

By SPyofgame, history, 4 weeks ago, In English,

I found these implementations ^^

Sorry, I am not sure if there are some corner cases or I calculated wrong complexity. If there are, please correct me.

I am wondering if there are some other implementations ^^ (you can comment below and I will add to the post)

Implementation 0: Trivial
Implementation 1: Optimized Trivial
Implementation 2: Naive Factorization
Implementation 3: Factorization
Implementation 4: Miller-rabin
Implementation 5: Sieve + Factorization
Implementation 6: Sieve + Miller-rabin + Pollard-rho
Implementation 7: Divisor Sum Sieve


Compilation:

Implementation Main Algorithm Time Complexity Space Complexity Coding Space Coding Complex
0. Trivial Implementation O(n) O(1) Short Simple
1. Trivial Implementation O(√n) O(1) Short Simple
2. Factorization + Math Math O(n ^ 2) ? O(1) Normal Normal
3. Factorization + Math Factorization O(n√n) O(1) Normal Normal
4. Factorization + Math Miller-rabin O(n * log^5(n)) O(1) Long Normal
5. Factorization + Math Sieve O(n) + O(log n) O(n) Normal Normal
6. Factorization + Math Pollard-rho O(√n) + O(√(√(n)) polylog n) query O(√n) + O(log n / log(log n)) query Very Long Complex


Planning:

  • Add relative blogs

  • Add some more implementations

  • Add tutorial & reasoning for each implementation

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

It is really useful for newcomers like us.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can add one simple sieve for divisor summation for all numbers from interval $$$[1 \dots N]$$$. For example, this is the solution for SPOJ problem DIVSUM:

Code

Also the main method for summation of the divisors of the single (not very large) number $$$N$$$ is prime factorization with ready prime list till $$$\sqrt{N}$$$. So you can easily solve SPOJ problem DIVSUM2:

Code

PS Please, pay attention that the SPOJ problems in question are about summation of proper divisors.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Insightful!!!!