Оптимизация вычисления делителей

Чтобы решить задачу эффективно, необходимо воспользоваться свойствами делителей чисел и оптимизировать вычисления, избегая прямого перебора всех чисел и их делителей в диапазоне $[a, b]$. Прямая реализация, которая вычисляет количество делителей для каждого числа в диапазоне, будет слишком медленной из-за большого размера возможного диапазона ($1 \leq a \leq b \leq 2^{31} - 1$).

Шаги решения

1. Понимание задачи: Нам нужно вычислить сумму количества делителей для каждого числа в диапазоне от $a$ до $b$, то есть:

   $$S = f(a) + f(a+1) + \dots + f(b)$$

   где $f(x)$ — количество делителей числа $x$.

2. Математическое преобразование: Известно, что сумма количества делителей для чисел от $1$ до $N$ равна:

   $$\sum_{x=1}^{N} f(x) = \sum_{d=1}^{N} \left\lfloor \frac{N}{d} \right\rfloor$$

   Это преобразование позволяет вычислить сумму делителей за более эффективное время.

3. Оптимизация вычислений: Для большого $N$ (до $2^{31} - 1$) прямой перебор всех делителей будет слишком медленным. Вместо этого воспользуемся свойством, что количество уникальных значений $\left\lfloor \frac{N}{d} \right\rfloor$ ограничено порядка $2 \sqrt{N}$. Это позволяет вычислить сумму за $O(\sqrt{N})$ времени.

4. Вычисление суммы в диапазоне $[a, b]$: Для получения суммы в заданном диапазоне, нужно вычислить:

   $$S(a, b) = \sum_{x=a}^{b} f(x) = \sum_{x=1}^{b} f(x) - \sum_{x=1}^{a-1} f(x)$$

   То есть, разность между суммой делителей от $1$ до $b$ и от $1$ до $a-1$.

Реализация на C++

Ниже представлен код на C++, который реализует описанный подход:

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// Функция для вычисления суммы количества делителей от 1 до N
ll sumDivisors(ll N) {
    ll res = 0;
    ll i = 1;
    // Суммируем floor(N / i) для i от 1 до sqrt(N)
    while (i * i <= N) {
        res += N / i;
        i++;
    }
    // Теперь обрабатываем оставшиеся значения floor(N / d)
    // где d < i, что эквивалентно k = floor(N / d) > sqrt(N)
    ll last = N / i;
    for(ll k = 1; k <= last; ++k){
        // d_min = floor(N / (k + 1)) + 1
        // d_max = floor(N / k)
        ll d_min = N / (k + 1) + 1;
        ll d_max = N / k;
        if(d_max < i) break; // уже обработали
        d_min = max(d_min, (ll)i);
        res += k * (d_max - d_min + 1);
    }
    return res;
}

int main(){
    ll a, b;
    // Чтение входных данных
    cin >> a >> b;
    // Вычисляем сумму делителей от 1 до b и от 1 до (a-1)
    ll sum_b = sumDivisors(b);
    ll sum_a_minus_1 = (a > 1) ? sumDivisors(a - 1) : 0;
    // Результат - разность двух сумм
    ll result = sum_b - sum_a_minus_1;
    cout << result;
    return 0;
}

Пояснение кода

1. Функция sumDivisors(ll N):

   • Цель: Вычислить сумму количества делителей для всех чисел от $1$ до $N$.
   • Метод:
     • Первый цикл: Проходим по всем $i$ от $1$ до $\sqrt{N}$, добавляя $\left\lfloor \frac{N}{i} \right\rfloor$ к результату. Это охватывает все делители, где $d \leq \sqrt{N}$.
     • Второй цикл: Обрабатываем оставшиеся значения $\left\lfloor \frac{N}{d} \right\rfloor$, где $d > \sqrt{N}$. Здесь $k = \left\lfloor \frac{N}{d} \right\rfloor$ принимает значения от $1$ до $\left\lfloor \frac{N}{i} \right\rfloor$, где $i$ — текущее значение после первого цикла.
     • Оптимизация: Используя свойства деления, избегаем повторного перебора и учитываем только уникальные значения $k$, уменьшая количество итераций до порядка $2 \sqrt{N}$.

2. Функция main():

   • Чтение входных данных: Считывает два числа $a$ и $b$.
   • Вычисление суммы делителей:
     • Вычисляет сумму делителей от $1$ до $b$ с помощью sumDivisors(b).
     • Вычисляет сумму делителей от $1$ до $a-1$ с помощью sumDivisors(a - 1), если $a > 1$.
   • Результат: Разность двух сумм дает искомую сумму делителей в диапазоне $[a, b]$.
   • Вывод результата: Печатает полученную сумму.

Обоснование эффективности

• Временная сложность: $O(\sqrt{N})$ для каждого вызова sumDivisors. Так как $N$ может быть до $2^{31} - 1$, $\sqrt{N}$ составляет примерно $46\,340$, что достаточно быстро даже для большого количества запросов.
• Пространственная сложность: $O(1)$, так как используется постоянное количество памяти независимо от входного размера.

Таким образом, данное решение оптимально с точки зрения асимптотической сложности и эффективно справляется с заданными ограничениями.