<aside> 💡 Tác giả: Muoii

</aside>

• Số ước của N = (q1 + 1)(q2 + 1)...(qk + 1)

• Sàng nguyên tố trên đoạn:

void range_eratosthenes(int L, int R)
{
    int range = R - L + 1;
    fill(isPrime, isPrime + range + 1, true);

    // Duyệt các bội của i từ bội nhỏ nhất thuộc đoạn [L, R].
    for (long long i = 2; i * i <= R; ++i)
        for (long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i)
            isPrime[j - L] = false;

    if (L == 1) isPrime[0] = false;
}

• Tích các ước của một số: sqrt(N)^(số ước)
• Tổng các ước của một số:

int64_t exponentiation(int A, int B)
{
    if (B == 0) return 1;

    int64_t half = exponentiation(A, B / 2);

    return (B & 1) ? half * half * A : half * half;
}

/// O(sqrt(N)) or O(NlogN)
/// Depend on the complexity to convert N to prime factors
int64_t get_sum_divisors(int N)
{
    if (N == 1) return 1;

    auto factors = to_prime_factors(N);
    int64_t sum_divisors = 1;

    for(auto p : factors)
    {
        int x = p.first;
        int cnt = p.second;

        sum_divisors *= ((exponentiation(x, cnt + 1) - 1) / (x - 1));
    }

    return sum_divisors;
}