Divisor Sum Implementations

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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: Trivial
/// Time  Complexity: O(n)
/// Space Complexity: O(1)

int main()
{
    int n = readInt();

    ll sum = 0;
    /// n = sigma(x | n % x == 0)
    for (int i = 1; i <= n; ++i) /// O(n)
        if (n % i == 0) /// If (i) is a divisor
            sum += i;
    
    cout << sum;
    return 0;
}

Implementation 1: Optimized Trivial

/// Implementation: Optimized Trivial
/// Time  Complexity: O(√n)
/// Space Complexity: O(1)

typedef long long ll;
int main()
{
    ll n = readLong();
    int sqrtn = sqrt(n);
    
    ll sum = 0;
    /// if (i) is a divisor then (n) / (i) is also a divisor
    for (ll i = 1; i <= sqrtn; ++i) /// O(√n)
    {
        if (n % i != 0) continue; /// If (i) not a divisor
        sum += i;
        ll t = n / i;
        if (i != t) sum += t;     /// If (t) is a unique divisor
    }
    
    cout << sum;
    return 0;
}

Implementation 2: Naive Factorization

/// Implementation: Naive | Multiplicative Formula
/// Time  Complexity: O(n ^ 2)
/// Space Complexity: O(1)

typedef long long ll;
inline ll pw(int x, int n) /// O(n)
{
    ll res = 1;
    for (int i = 1; i <= n; ++i) res *= x;
    return res;
}

bool isPrime(int n) /// O(n)
{
    int cnt = 0;
    for (int i = 1; i <= n; ++i) cnt += (n % i == 0);
    return (cnt == 2);
}

int main() /// O(n ^ 2) ?
{
    int n = readInt();

    ll sum = 1;
    /// n = p1 ^ f1 * p2 ^ 2 * ... * pk ^ fk
    /// sum = ∏(divisor prime p){ p ^ (f + 1) - 1) / (p - 1) }
    for (int i = 1; i <= n; ++i) /// O(n * f(n)) ≤ O(n + divisor_count ^ 2) ≤ O(n ^ 2)
    {
        if (n % i != 0) continue;
        if (isPrime(i) == false) continue; /// O(i)
        
        int p = i, f = 0;
        do f++, n /= p; while (n % p == 0);  /// O(log_p(n))
        sum *= (pw(p, f + 1) - 1) / (p - 1); /// O(f)
    }
    
    cout << sum;
    return 0;
}

Implementation 3: Factorization

/// Implementation: Optimized | Multiplicative Formula
/// Time  Complexity: O(n√n)
/// Space Complexity: O(1)

typedef long long ll;
inline ll pw(ll x, ll n) /// O(log n)
{
    ll res = 1;
    for (; n > 0; x = x * x, n >>= 1)
        if (n & 1) res = res * x;
    
    return res;
}

inline bool isPrime(ll n) /// O(sqrt n)
{ 
    if (n < 2) return false; 
    if (n < 4) return true; 
    if (n % 2 == 0 || n % 3 == 0) return false; 
  
    int sqrtn = sqrt(n);
    for (ll i = 5; i <= sqrtn; i += 6) 
        if ((n % i == 0) || (n % (i + 2) == 0)) 
            return false; 
  
    return true; 
} 

int main() /// O(n√n)
{
    ll n = readLong();

    ll sum = 1;
    /// n = p1 ^ f1 * p2 ^ 2 * ... * pk ^ fk
    /// sum = ∏(divisor prime p){ p ^ (f + 1) - 1) / (p - 1) }
    for (ll i = 1; i <= n; ++i) /// O(n * f(n)) ≤ O(n + sqrt(divisor_count)) ≤ O(n * sqrt(n))
    {
        if (n % i != 0) continue;
        if (isPrime(i) == false) continue; /// O(sqrt i)  

        ll p = i; int f = 0;
        do f++, n /= p; while (n % p == 0);  /// O(log_p(n))
        sum *= (pw(p, f + 1) - 1) / (p - 1); /// O(log f)
    }
    
    cout << sum;
    return 0;
}

Implementation 4: Miller-rabin

/// Implementation: Miller-rabin Primality Test | Multiplicative Formula
/// Time  Complexity: O(n * log^5(n))
/// Space Complexity: O(1)

typedef long long ll;
inline ll bigmodMul(ll a, ll b, ll m = MOD) /// O(log n)
{
    ll res = 0;
    for (a %= m, b %= m; b > 0; a <<= 1, b >>= 1) {
        if (a >= m) a -= m;
        if (b & 1) { res += a; if (res >= m) res -= m; }
    }

    return res;
}
inline ll bigmodPow(ll x, ll n, ll m = MOD) /// O(log^2(n))
{
    ll res = 1;
    for (x %= m; n > 0; x = bigmodMul(x, x, m), n >>= 1)
        if (n & 1) res = bigmodMul(res, x, m);
    
    return res;
}

inline ll pw(ll x, ll n) /// O(log n)
{
    ll res = 1;
    for (; n > 0; x = x * x, n >>= 1)
        if (n & 1) res = res * x;
    
    return res;
}

inline bool isPrime(ll p) /// O(log^5(p)) - O(log p) rounds performed - O(log^2(p)) primality tests - O(log^2(p)) calculation
{
    if (p < 2) return false;
    if (p < 4) return true;
    if (p % 2 == 0 || p % 3 == 0) return false;
 
    ll q = p - 1;
    int k = 0;
    while ((q & 1) == 0) /// O(log p)
        q >>= 1, k++;
 
    ll a = rand() % (p - 4) + 2;
    ll t = bigmodPow(a, q, p); /// O(log^2(q))
 
    bool ok = (t == 1) || (t == p-1);
    for (int i = 1; i <= k && !ok; i++) { /// O(log k * log t)
        t = bigmodMul(t, t, p); /// O(log t)
        ok = (t == p - 1);
    }
 
    return ok;
}

int main() /// O(n * log5(n))
{
    ll n = readLong();
    ll sum = 1;
    /// n = p1 ^ f1 * p2 ^ 2 * ... * pk ^ fk
    /// sum = ∏(divisor prime p){ p ^ (f + 1) - 1) / (p - 1) }
    for (ll i = 1; i <= n; ++i) /// O(n * f(n)) ≤ O(divisor_count * log^5(n)) ≤ O(n * log^5(n))
    {
        if (n % i != 0) continue;
        if (isPrime(i) == false) continue; /// O(log^5(i))

        ll p = i; int f = 0;
        do f++, n /= p; while (n % p == 0);  /// O(log_p(n))
        sum *= (pw(p, f + 1) - 1) / (p - 1); /// O(log f)
    }
    
    cout << sum;
    return 0;
}

Implementation 5: Sieve + Factorization

/// Implementation: Sieve | Factorization | Multiplicative Formula
/// Time  Complexity: O(n) precalculation + O(log n) query
/// Space Complexity: O(n) sieve + O(1) query

typedef long long ll;
inline ll pw(ll x, ll n) /// O(log n)
{
    ll res = 1;
    for (; n > 0; x = x * x, n >>= 1)
        if (n & 1) res = res * x;
    
    return res;
}

vector<int> prime; /// List of prime numbers
vector<int> lpf;   /// lpf[x] = Lowest_Prime_Factor of x

void sieve(int lim = LIM) /// O(n)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2);

    for (int i = 3; i <= lim; i += 2)
    {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(lpf) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

int main()
{
    int n = readInt();
    sieve(n); /// O(n) for sieving

    ll sum = 1;
    /// n = p1 ^ f1 * p2 ^ 2 * ... * pk ^ fk
    /// sum = ∏(divisor prime p){ p ^ (f + 1) - 1) / (p - 1) }
    for (int p, f; n > 1; ) /// O(log n)
    {
        for (p = lpf[n], f = 0; (n > 1) && (p == lpf[n]); n /= p) f++; /// O(log n)
        sum *= (pw(p, f + 1) - 1) / (p - 1);                           /// O(log n)
    }
    
    cout << sum;
    return 0;
}

Implementation 6: Sieve + Miller-rabin + Pollard-rho

/// Implementation: Sieve | Factorization | Pollard-rho | Miller-rabin | Multiplicative Formula
/// Time  Complexity: O(√n) precal + O(√(√(n)) polylog n) query
/// Space Complexity: O(√n) sieve + O(log n / log(log n)) query

const int MOD = 1e9 + 7;
typedef long long ll;
inline ll bigmodMul(ll a, ll b, ll m = MOD) /// O(log n)
{
    ll res = 0;
    for (a %= m, b %= m; b > 0; a <<= 1, b >>= 1) {
        if (a >= m) a -= m;
        if (b & 1) { res += a; if (res >= m) res -= m; }
    }

    return res;
}
inline ll bigmodPow(ll x, ll n, ll m = MOD) /// O(log^2(n))
{
    ll res = 1;
    for (x %= m; n > 0; x = bigmodMul(x, x, m), n >>= 1)
        if (n & 1) res = bigmodMul(res, x, m);
    
    return res;
}

inline ll pw(ll x, ll n) /// O(log n)
{
    ll res = 1;
    for (; n > 0; x = x * x, n >>= 1)
        if (n & 1) res = res * x;
    
    return res;
}

inline bool isPrime(ll p) /// O(log^5(p)) - O(log p) rounds performed - O(log^2(p)) primality tests - O(log^2(p)) calculation
{
    if (p < 2) return false;
    if (p < 4) return true;
    if (p % 2 == 0 || p % 3 == 0) return false;
 
    ll q = p - 1;
    int k = 0;
    while ((q & 1) == 0) /// O(log p)
        q >>= 1, k++;
 
    ll a = rand() % (p - 4) + 2;
    ll t = bigmodPow(a, q, p); /// O(log^2(q))
 
    bool ok = (t == 1) || (t == p-1);
    for (int i = 1; i <= k && !ok; i++) { /// O(log k * log t)
        t = bigmodMul(t, t, p); /// O(log t)
        ok = (t == p - 1);
    }
 
    return ok;
}

map<int, int> M;
int sqrtn;
ll sum = 0; 

vector<int> prime; /// List of prime numbers
vector<int> lpf;   /// lpf[x] = Lowest_Prime_Factor of x

void sieve(int lim = LIM) /// O(n)
{
    prime.assign(1, 2);
    lpf.assign(lim + 1, 2); /// O(n)

    for (int i = 3; i <= lim; i += 2) /// O(n)
    {
        if (lpf[i] == 2) prime.pb(lpf[i] = i);
        for (int j = 0; j < sz(lpf) && prime[j] <= lpf[i] && prime[j] * i <= lim; ++j)
            lpf[prime[j] * i] = prime[j];
    }
}

ll rho(ll n, ll c) {  /// O(√(√(n)) * polylog n)
    ll x = 2, y = 2, i = 2, k = 2, d;
    while (true) {
        x = (bigmodMul(x, x, n) + c); /// O(log n)
        if (x >= n)	x -= n;
        d = __gcd(abs(x - y), n);     /// O(log n)
        if (d > 1) return d;
        if (i++ == k) y = x, k <<= 1;
    }
    return n;
}
 
void big_fact(ll n) { /// O(√(√(n)) * polylog n)
    if (n == 1) /// O(1)
        return ;
 
    if (n < 1e+9) { /// O(√(n) / ln(√(n)) * log n / log log n)
        for (int p : prime) /// O(pi(√(n)) * log(M.size)) = O(√(n) / ln(√(n)) * log n / log(log n))
        {
            if (p > sqrtn) break;
            while (n % p == 0) M[p]++, n /= p; /// O(log_p(n) * log(M.size)) = O(log_p(n) * log(n) / log(log n))
        }

        if (n > 1) M[n]++; /// O(log(M.size)) = O(log n / log(log n))
        return ;
    }
 
    if (isPrime(n))            /// O(log^5(n))
        return M[n]++, void(); /// O(log(M.size)) = O(log n / log(log n))
 
    ll d = n;
    for (int i = 2; d == n; i++) /// O(√(√(n)) * polylog n)
        d = rho(n, i);           /// O(√(√(n)) * polylog n)
 
    big_fact(    d);
    big_fact(n / d);
}

int main() /// O(√n + √(√(n)) * polylog n)
{
    ll n;
    cin >> n;

    sqrtn = sqrt(n);   /// O(√(n))   
    sieve(sqrtn);      /// O(√(n))
    
    srand(time(NULL));
    big_fact(n);       /// O(√(√(n)) * polylog n)
    
    ll sum = 1;
    /// n = ∏(e ∈ M){ e.fi ^ e.se }
    /// sum = ∏(divisor prime e.fi){ e.fi ^ (e.se + 1) - 1) / (e.fi - 1) }
    for (pi e : M)     /// O(log n / log(log n))
        sum *= (pw(e.fi, e.se + 1) - 1) / (e.fi - 1); /// O(log n)

    cout << sum;    
    return 0;
}

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))	Very Long	Complex

Planning:

Add relative blogs
Add some more implementations
Add tutorial & reasoning for each implementation

Rev.	Кто	Когда	Δ	Комментарий
en13	SPyofgame	2020-07-09 17:21:47	288
en12	SPyofgame	2020-06-07 03:18:33	776
en11	SPyofgame	2020-06-06 17:29:51	262
en10	SPyofgame	2020-06-06 17:27:09	258
en9	SPyofgame	2020-06-06 17:26:20	10
en8	SPyofgame	2020-06-06 17:25:50	212
en7	SPyofgame	2020-06-06 17:18:09	1	Tiny change: 'iler>\n\n# Compilat' -> 'iler>\n\n## Compilat'
en6	SPyofgame	2020-06-06 17:17:49	1191
en5	SPyofgame	2020-06-06 16:56:29	205
en4	SPyofgame	2020-06-06 06:22:27	31
en3	SPyofgame	2020-06-06 06:15:08	33	Tiny change: '# Divisor Sum Implementations\n\n## I found' -> '## I found'
en2	SPyofgame	2020-06-06 06:14:49	5	Tiny change: 'ations\n\nI found th' -> 'ations\n\n## I found th'
en1	SPyofgame	2020-06-06 06:14:21	10906	Initial revision (published)

I found these implementations ^^

Compilation:

Planning:

История