Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### SPyofgame's blog

By SPyofgame, history, 3 years ago,

### 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

• +40

| Write comment?
 » 3 years ago, # |   0 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#include #define MAXN 500000 int sum[MAXN+1]; void sieve( void ) { int i, j; for( i = 1; i <= MAXN; ++i) for( j = i+i; j <= MAXN; j += i) sum[j] += i; } int main( void ) { int t; sieve(); scanf( "%d", &t); while( t-- > 0 ) { int n; scanf( "%d", &n); printf( "%d\n", sum[n]); } return 0; } 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#include #if defined( _WIN32 ) typedef __int64 az_int64_t; typedef unsigned __int64 az_uint64_t; #define I64(x) x ## I64 #define F64 "I64" #else typedef long long az_int64_t; typedef unsigned long long az_uint64_t; #define I64(x) x ## ll #define F64 "ll" #endif #define LIMIT 100000000 #define HAS(_n) (pbits[(_n)>>5] & (1u << ((_n) & 0x1f))) #define SET(_n) (pbits[(_n)>>5] |= (1u << ((_n) & 0x1f))) unsigned int pbits[LIMIT/32+1]; int pc, pr[LIMIT/10]; void sieve( void ) { int i, j; pc = 0; for( i = 2; i <= LIMIT; ++i) { if( !HAS( i ) ) pr[pc++] = i; for( j = 0; j < pc && i * pr[j] <= LIMIT; ++j) { int num = i * pr[j]; SET( num ); if( i % pr[j] == 0 ) break; } } } az_int64_t solution( az_int64_t n ) { az_int64_t o = n, ans = 1; int i; for( i = 0; i < pc && (az_int64_t) pr[i] * pr[i] <= n; ++i) { int count = 0; az_int64_t sum = 1, pw = 1; while( n % pr[i] == 0 ) { pw *= pr[i]; sum += pw; count++; n /= pr[i]; } if( count > 0 ) ans *= sum; } if( n > 1 ) ans *= n + 1; return ans - o; } int main( void ) { int t; sieve(); scanf( "%d", &t); while( t-- > 0 ) { az_int64_t n; scanf( "%" F64 "d", &n); printf( "%" F64 "d\n", solution( n )); } return 0; } PS Please, pay attention that the SPOJ problems in question are about summation of proper divisors.
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 Thank you for the solutions ^^
 » 2 months ago, # |   0 In the comment you have explain the code but in one comment you have missed one thing which is- /// n = p1 ^ f1 * p2 ^f2 * ... * pk ^ fk //correct one/// n = p1 ^ f1 * p2 ^ 2 * ... * pk ^ fk //wrong one