Problem 485: Maximum Number of Divisors

Mathematical Foundation

Theorem 1 (Divisor function via sieve). For any positive integer $n$,

The values $d(1), d(2), \ldots, d(L)$ can be computed simultaneously by iterating: for each $j = 1, 2, \ldots, L$, increment $d[j], d[2j], d[3j], \ldots, d[\lfloor L/j \rfloor \cdot j]$ by 1.

Proof. By definition, $d(n)$ counts the number of positive divisors of $n$. The sieve procedure adds 1 to $d[n]$ exactly once for each divisor $j$ of $n$ (since $j \mid n$ iff $n$ appears in the arithmetic progression $j, 2j, 3j, \ldots$). The total work is $\sum_{j=1}^L \lfloor L/j \rfloor = O(L \ln L)$. $\square$

Theorem 2 (Sliding window maximum via monotone deque). Given an array $a[1 \ldots L]$ and window size $k$, the sequence of window maxima $M_i = \max(a[i], \ldots, a[i+k-1])$ for $i = 1, \ldots, L - k + 1$ can be computed in $O(L)$ amortized time using a monotone deque.

Proof. Maintain a deque $D$ of indices, invariant: $D$ is non-empty, indices are in increasing order, and $a[D[\text{front}]] \ge a[D[\text{front}+1]] \ge \cdots \ge a[D[\text{back}]]$ (weakly decreasing in $a$-values).

For each new index $i$:

1. While $D$ is non-empty and $a[D.\text{back}] \le a[i]$: pop from back.
2. Push $i$ to back.
3. While $D.\text{front} < i - k + 1$: pop from front (out of window).
4. The window maximum is $a[D.\text{front}]$.

Correctness: After step 1, all indices remaining in $D$ have $a$-values strictly greater than $a[i]$, and $i$ is appended. The front is always the index of the maximum value in the current window because: (a) all indices in $D$ are within the window (step 3 ensures this), and (b) any index $j < i$ with $a[j] \le a[i]$ was removed in step 1 (either when $i$ was processed or earlier), so the front has the largest $a$-value.

Amortized $O(1)$: Each index is pushed onto $D$ exactly once and popped at most once from the back and at most once from the front. Over $L$ iterations, the total number of push and pop operations is at most $3L$. $\square$

Lemma 1 (Divisor count upper bound). For $n \le 10^8 + 10^5$, we have $d(n) \le 768$. More precisely, the maximum value of $d(n)$ for $n \le 10^8$ is achieved at highly composite numbers.

Proof. By the theory of highly composite numbers (Ramanujan, 1915), the divisor function grows sub-polynomially. For $n \le 10^8$, an exhaustive sieve confirms $d(n) \le 768$. $\square$

Editorial

d(i) = number of divisors of i. M(n,k) = max(d(n), d(n+1), …, d(n+k-1)). Given: sum M(n,10) for n=1..100 = 432. Find: sum M(n, 10^4) for n=1..10^8. We divisor count sieve. We then sliding window maximum via monotone deque. Finally, maintain decreasing invariant.

Pseudocode

Divisor count sieve
Sliding window maximum via monotone deque
Maintain decreasing invariant
Remove out-of-window front
Once window is full (i >= k), record the maximum

Complexity Analysis

• Time: $O(L \log L)$ for the divisor sieve (where $L = N + k - 1 \approx 1.0001 \times 10^8$), plus $O(L)$ for the sliding window. Total: $O(L \log L)$.
• Space: $O(L)$ for the divisor array, plus $O(k)$ for the deque. Total: $O(L)$.

For $N = 10^8$ and $k = 10^5$, $L \approx 10^8$, so the sieve requires approximately $10^8 \times \ln(10^8) \approx 1.8 \times 10^9$ operations and $\sim 400$ MB of memory (using 32-bit integers for $d$).

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Parameters
    const int N = 100;      // Change to 100000000 for full problem
    const int K = 10;       // Change to 10000 for full problem
    const int L = N + K - 1;

    // Divisor count sieve
    vector<int> d(L + 1, 0);
    for (int j = 1; j <= L; j++) {
        for (int m = j; m <= L; m += j) {
            d[m]++;
        }
    }

    // Sliding window maximum using monotone deque
    deque<int> dq;
    long long total = 0;

    for (int i = 1; i <= L; i++) {
        while (!dq.empty() && d[dq.back()] <= d[i])
            dq.pop_back();
        dq.push_back(i);

        int n = i - K + 1;
        if (n >= 1) {
            while (dq.front() < n)
                dq.pop_front();
            total += d[dq.front()];
        }
    }

    cout << "Sum M(n," << K << ") for n=1.." << N << " = " << total << endl;

    // For N=100, K=10: expected 432
    if (N == 100 && K == 10) {
        assert(total == 432);
    }

    return 0;
}

"""
Problem 485: Maximum number of divisors
d(i) = number of divisors of i.
M(n,k) = max(d(n), d(n+1), ..., d(n+k-1)).
Given: sum M(n,10) for n=1..100 = 432.
Find: sum M(n, 10^4) for n=1..10^8.
"""

from collections import deque

def divisor_count_sieve(limit: int) -> list:
    """Compute d(n) for n = 0..limit using a sieve."""
    d = [0] * (limit + 1)
    for j in range(1, limit + 1):
        for multiple in range(j, limit + 1, j):
            d[multiple] += 1
    return d

def sliding_window_max_sum(d: list, n_max: int, k: int):
    """Sum of sliding window maxima of d[1..n_max+k-1] with window size k."""
    dq = deque()  # stores indices, d-values decreasing
    total = 0

    for i in range(1, n_max + k):
        # Remove from back if current d[i] >= d[back]
        while dq and d[dq[-1]] <= d[i]:
            dq.pop()
        dq.append(i)

        # Remove from front if out of window
        # Window for position n: indices n..n+k-1
        # When i = n+k-1, window starts at n = i - k + 1
        n = i - k + 1
        if n >= 1:
            while dq[0] < n:
                dq.popleft()
            total += d[dq[0]]

    return total

def solve(n_max: int, k: int):
    """Solve the problem for given N and k."""
    limit = n_max + k - 1
    d = divisor_count_sieve(limit)
    return sliding_window_max_sum(d, n_max, k)

# Verify with small example
answer_check = solve(100, 10)
print(f"Sum M(n,10) for n=1..100 = {answer_check}")

# For the full problem: solve(10**8, 10**4) -- requires ~10^8 memory
# Uncomment for full computation (takes significant time/memory):
# answer = solve(10**8, 10**4)
# print(f"Sum M(n,10^4) for n=1..10^8 = {answer}")