Мотивация и контекст

Представьте задачу: вычислить ∑{i=1}^{N} ∑{j=1}^{N} gcd(i, j) при N = 10^7. Наивный подход — O(N² log N), явно непригодный. Но с помощью мультипликативных функций, дзета-функции и метода гиперболического суммирования Дирихле это решается за O(N log log N) или даже O(N^{2/3}).

В этой главе мы изучим:

• Дзета-функцию Римана и её роль в теории простых чисел
• Средние значения мультипликативных функций (сколько в среднем делителей у числа n?)
• Метод гиперболической суммации — элегантная техника для "диагональных" сумм
• Как все эти идеи применяются для оптимизации алгоритмов в CP

Это не просто теория — асимптотические оценки помогают предсказывать время работы алгоритмов и выбирать правильные подходы.

---

Теория

Дзета-функция Римана

Определение. Дзета-функция Римана:

ζ(s) = ∑_{n=1}^{∞} 1/n^s = ∏_p 1/(1 − p^{−s})  (Re(s) > 1)

Второе равенство — произведение Эйлера — следует из основной теоремы арифметики: каждое n единственно представляется как произведение простых, и геометрические ряды ∑ p^{−ks} = 1/(1−p^{−s}) перемножаются.

Аналитическое продолжение. ζ(s) продолжается до мероморфной функции на всю комплексную плоскость с единственным простым полюсом в s = 1: ζ(s) ≈ 1/(s−1) при s → 1.

Значения в целых точках:

• ζ(2) = π²/6 ≈ 1.6449 (задача Базеля)
• ζ(4) = π⁴/90
• ζ(2k) = (−1)^{k+1} · (2π)^{2k} · B_{2k} / (2 · (2k)!), где B_{2k} — числа Бернулли

Связь с теорией простых чисел. Простые числа кодируются в нулях ζ(s). Гипотеза Римана (нерешённая): все нетривиальные нули ζ(s) лежат на прямой Re(s) = 1/2.

Ряды Дирихле и мультипликативные функции

Ряд Дирихле функции f: A(s) = ∑_{n=1}^{∞} f(n)/n^s.

Перемножение рядов Дирихле. Если A(s) = ∑ a(n)/n^s и B(s) = ∑ b(n)/n^s, то:

A(s) · B(s) = ∑_{n=1}^{∞} c(n)/n^s,   c(n) = ∑_{d|n} a(d) · b(n/d)  (свёртка Дирихле)

Мультипликативные функции f: если gcd(m,n)=1, то f(mn) = f(m)·f(n). Для них:

∑_{n=1}^{∞} f(n)/n^s = ∏_p (∑_{k=0}^{∞} f(p^k)/p^{ks})  — локальные факторы

Таблица рядов Дирихле:

Средние значения мультипликативных функций

Теорема Дирихле о среднем числе делителей:

∑_{n=1}^{N} d(n) = N ln N + (2γ − 1)N + O(N^{1/2})

где γ ≈ 0.5772 — постоянная Эйлера-Маскерони.

Доказательство (метод гиперболической суммации). Заметим, что d(n) = ∑_{d|n} 1 = #{(a,b) : ab = n}. Тогда:

∑_{n=1}^{N} d(n) = #{(a,b) : 1 ≤ a,b, ab ≤ N} = #{(a,b) : ab ≤ N}

Это число решёточных точек в гиперболе xy ≤ N. Считаем через разбиение:

#{ab ≤ N} = ∑_{a=1}^{N} ⌊N/a⌋ = ∑_{a≤√N} ⌊N/a⌋ + ∑_{b≤√N} ⌊N/b⌋ − ⌊√N⌋²
           ≈ 2N ∑_{a≤√N} 1/a − N ≈ 2N (ln√N + γ) − N = N ln N + (2γ−1)N

Теорема о среднем φ(n):

∑_{n=1}^{N} φ(n) = 3N²/π² + O(N log N)

Эквивалентная форма: 1/N ∑_{n=1}^{N} φ(n)/n → 6/π² ≈ 0.6079. Это доля пар (a, n) с gcd(a, n) = 1 среди всех пар.

Доказательство. φ(n) = n · ∏{p|n} (1 − 1/p). Используем формулу φ = μ * id (свёртка Дирихле). Тогда ∑{n≤N} φ(n) = ∑{n≤N} ∑{d|n} μ(d) · (n/d) = ∑{d≤N} μ(d)/d · ∑{k≤N/d} k = ∑{d≤N} μ(d)/d · N²/(2d²) + ... = N²/2 · ∑{d=1}^{∞} μ(d)/d² + O(N log N) = N²/2 · 1/ζ(2) + O(N log N) = 3N²/π². □

Формула Мертенса:

∑_{p≤N} 1/p = ln ln N + M + O(1/ln N)

где M ≈ 0.2615 — постоянная Мейселя-Мертенса.

Доказательство (набросок). Использует логарифмическое произведение Эйлера: ln ζ(s) = ∑_p ∑_k p^{−ks}/k. При s → 1+ получаем ∑_p 1/p → ln ln N через теорему Дирихле о простых в прогрессиях.

Метод гиперболической суммации Дирихле

Метод позволяет вычислять суммы вида:

∑_{n=1}^{N} f(n)  или  ∑_{n=1}^{N} g(⌊N/n⌋)

эффективнее, чем прямым перебором.

Ключевое наблюдение. Функция ⌊N/n⌋ принимает не более 2√N различных значений (при n ≤ √N — все различны; при n > √N — все ≤ √N). Блок одинаковых значений: ⌊N/n⌋ = k при n ∈ [⌊N/(k+1)⌋+1, ⌊N/k⌋].

Алгоритм суммирования: вместо перебора всех n от 1 до N, перебираем блоки одинакового ⌊N/n⌋ — O(√N) блоков.

ll sum_floor(ll N, auto g) {
    // Вычисляет ∑_{k=1}^{N} g(⌊N/k⌋) за O(√N)
    ll result = 0;
    ll k = 1;
    while (k <= N) {
        ll q = N / k;
        ll last = N / q; // последнее k с ⌊N/k⌋ = q
        result += g(q) * (last - k + 1);
        k = last + 1;
    }
    return result;
}

Теорема (основная лемма гиперболического суммирования). Для мультипликативных f, g:

∑_{n=1}^{N} (f * g)(n) = ∑_{a≤U} f(a) · G(⌊N/a⌋) + ∑_{b≤N/U} g(b) · F(⌊N/b⌋) − F(U) · G(N/U)

где F(n) = ∑{k=1}^{n} f(k), G(n) = ∑{k=1}^{n} g(k), U = √N.

Это разбивает двойную сумму по гиперболе ab ≤ N: при a ≤ √N берём ∑a f(a) · ∑{b≤N/a} g(b), при b ≤ √N — аналогично, вычитая дважды посчитанный квадрат.

Применение: вычисление ∑_{n≤N} d(n) за O(N^{1/2}). Уже разобрано выше.

Применение: вычисление ∑_{n≤N} φ(n) за O(N^{1/2}). Используем φ = μ * id, F(n) = n(n+1)/2 (сумма id), M(n) = ∑_{k≤n} μ(k).

Решето Линника для мультипликативных функций

Для вычисления ∑_{n=1}^{N} f(n) для мультипликативной f используем числовое решето:

// Перемножение мультипликативных функций через решето
// За O(N log log N) — количество операций ≈ N ∑_{p≤N} 1/p ≈ N ln ln N
vector<ll> sieve_multiplicative(int N, auto f_prime_power) {
    vector<ll> f(N + 1, 0);
    vector<int> primes;
    vector<bool> is_composite(N + 1, false);
    f[1] = 1;
    for (int n = 2; n <= N; n++) {
        if (!is_composite[n]) {
            primes.push_back(n);
            f[n] = f_prime_power(n, 1); // f(p^1)
        }
        for (int p : primes) {
            if ((ll)n * p > N) break;
            is_composite[n * p] = true;
            if (n % p == 0) {
                // nq = p^k * m, gcd(m, p) = 1
                // f(n*p) = f(p^{k+1}) * f(m) / f(p^k) * f(m) = ...
                // Требует хранения p^k
                // (упрощено)
                break;
            } else {
                f[n * p] = f[n] * f[p];
            }
        }
    }
    return f;
}

Полная реализация линейного решета с хранением p^k для каждого n — стандартный инструмент.

Асимптотические оценки в анализе алгоритмов CP

Анализ решета Эратосфена. Число операций = ∑_{p≤N} N/p ≈ N ln ln N (формула Мертенса).

Анализ Pollard ρ. Ожидаемое число итераций для нахождения делителя p числа n = O(√p) — birthday paradox. Для n = p·q с p ≈ q ≈ √n: O(n^{1/4}) итераций.

Среднее число простых делителей. Ω(n) = ∑{p^k | n, k≥1} 1 — общее число простых делителей с кратностью. Среднее ∑{n≤N} Ω(n)/N ≈ ln ln N.

Следствие для алгоритмов: факторизация случайного числа n перебирает в среднем O(ln ln n) ≈ 4 малых простых делителя до перехода к Полларду — это объясняет, почему предварительное пробное деление на первые 100 простых существенно ускоряет факторизацию.

---

Ключевые формулы

---

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

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

// ==================== Функция Мёбиуса и связанные ====================

// Линейное решето для μ, φ, d (число делителей)
struct MultiplicativeSieve {
    int N;
    vector<int> mu;         // функция Мёбиуса
    vector<ll> phi;         // φ(n) = Эйлер
    vector<int> d;          // d(n) = число делителей
    vector<int> primes;
    vector<int> min_prime;  // минимальный простой делитель
    vector<int> prime_cnt;  // v_p(n) для минимального p

    MultiplicativeSieve(int N) : N(N), mu(N+1), phi(N+1), d(N+1),
                                  min_prime(N+1, 0), prime_cnt(N+1, 0) {
        vector<bool> is_composite(N+1, false);
        mu[1] = 1; phi[1] = 1; d[1] = 1;
        for (int n = 2; n <= N; n++) {
            if (!is_composite[n]) {
                primes.push_back(n);
                min_prime[n] = n;
                prime_cnt[n] = 1;
                mu[n] = -1;
                phi[n] = n - 1;
                d[n] = 2;
            }
            for (int p : primes) {
                if ((ll)n * p > N) break;
                int np = n * p;
                is_composite[np] = true;
                min_prime[np] = p;
                if (n % p == 0) {
                    // p | n: p^{prime_cnt[n]+1} || np
                    prime_cnt[np] = prime_cnt[n] + 1;
                    mu[np] = 0;
                    phi[np] = phi[n] * p;
                    // d(np) = d(n) / (prime_cnt[n]+1) * (prime_cnt[n]+2)
                    d[np] = d[n] / (prime_cnt[n] + 1) * (prime_cnt[n] + 2);
                    break;
                } else {
                    // gcd(n, p) = 1
                    prime_cnt[np] = 1;
                    mu[np] = -mu[n];
                    phi[np] = phi[n] * (p - 1);
                    d[np] = d[n] * 2;
                }
            }
        }
    }

    // Префиксные суммы
    vector<ll> prefix_mu() {
        vector<ll> M(N+1);
        M[0] = 0;
        for (int i = 1; i <= N; i++) M[i] = M[i-1] + mu[i];
        return M;
    }
};

// ==================== Метод гиперболической суммации ====================

// Вычислить ∑_{n=1}^{N} d(n) за O(√N)
ll sum_divisors_count(ll N) {
    ll result = 0;
    ll k = 1;
    while (k <= N) {
        ll q = N / k;
        ll last = N / q;
        result += q * (last - k + 1);
        k = last + 1;
    }
    // Это ∑_{k=1}^{N} ⌊N/k⌋ = ∑_{n=1}^{N} d(n)
    return result;
}

// Вычислить ∑_{n=1}^{N} ⌊N/n⌋ за O(√N) — то же самое
ll sum_floor_div(ll N) {
    ll res = 0;
    for (ll k = 1, last; k <= N; k = last + 1) {
        ll q = N / k;
        last = N / q;
        res += q * (last - k + 1);
    }
    return res;
}

// Вычислить ∑_{n=1}^{N} φ(n) за O(N^{2/3}) используя:
// ∑_{n=1}^{N} φ(n) = N(N+1)/2 - ∑_{d=2}^{N} ∑_{n=1}^{⌊N/d⌋} φ(n) ... (рекуррентно)
// или через ∑φ(n) = (1/2)(1 + ∑_{d|n, d<n} μ(d) * ⌊N/d⌋ * ⌊N/d + 1⌋) ...
// Проще: φ использует Мёбиус

// Функция для вычисления ∑_{k=1}^{N} φ(k) за O(N^{2/3}) методом Люси Бедрён
// (используем рекуррентность через Мёбиус)
ll euler_sum(ll N) {
    // Простая версия: O(N) через линейное решето
    // Для O(N^{2/3}) используется метод "черно-белых клеток" Люси
    // Пока даём O(N log log N):
    MultiplicativeSieve sieve((int)min(N, (ll)1e7));
    ll res = 0;
    for (int i = 1; i <= min(N, (ll)1e7); i++) res += sieve.phi[i];
    return res;
}

// ==================== Суммирование гиперболическим методом ====================

// ∑_{1≤a,b≤N, gcd(a,b)=1} 1 = ∑_{n=1}^{N} φ(n) * 2 - 1
// Через инверсию Мёбиуса:
// #{(a,b): gcd(a,b)=1, a,b≤N} = ∑_{d=1}^{N} μ(d) * ⌊N/d⌋²

ll count_coprime_pairs(ll N) {
    // O(√N) через гиперболический метод
    // Нужны значения M(k) = ∑_{i=1}^{k} μ(i) — функция Мертенса
    // Но вычислить M(k) за O(1) сложно; используем O(N^{2/3}) метод
    // Для простоты: предварительное вычисление μ до N
    // (только для N ≤ 10^7)
    int n = (int)N;
    MultiplicativeSieve sieve(n);
    ll res = 0;
    for (int d = 1; d <= n; d++) {
        if (sieve.mu[d] != 0) {
            ll q = N / d;
            res += sieve.mu[d] * q * q;
        }
    }
    return res;
}

// ==================== Числовой NTT-свёртка Дирихле ====================

// Умножение мультипликативных функций f * g через "решето Дирихле"
// За O(N log N) или O(N log log N)
vector<ll> dirichlet_convolution(vector<ll>& f, vector<ll>& g, int N) {
    vector<ll> h(N + 1, 0);
    for (int d = 1; d <= N; d++) {
        if (f[d] == 0) continue;
        for (int k = d; k <= N; k += d) {
            h[k] += f[d] * g[k / d];
        }
    }
    return h;
}

// Инверсия Дирихле: найти g = f^{-1} (свёртка Дирихле)
// Тогда g * f = ε (дельта-функция, ε(1)=1, ε(n)=0 при n>1)
// g(1) = 1/f(1), g(n) = -1/f(1) * ∑_{d|n, d<n} g(d) * f(n/d)
vector<ll> dirichlet_inverse(vector<ll>& f, int N, ll mod = 0) {
    vector<ll> g(N + 1, 0);
    g[1] = 1; // f[1] = 1 assumed
    for (int n = 2; n <= N; n++) {
        for (int d = 1; d < n; d++) {
            if (n % d == 0) {
                g[n] -= g[d] * f[n / d];
            }
        }
        if (mod) g[n] = ((g[n] % mod) + mod) % mod;
    }
    return g;
}

// ==================== Суммирование ∑gcd с использованием Мёбиуса ================

// ∑_{i=1}^{N} ∑_{j=1}^{N} gcd(i,j) за O(N log N)
// = ∑_{d=1}^{N} d * #{(i,j) : gcd(i,j)=d} = ∑_{d=1}^{N} d * #{(i,j): i,j≤N/d, gcd(i,j)=1}
// = ∑_{d=1}^{N} d * ∑_{k=1}^{N/d} μ(k) * ⌊N/(dk)⌋²
// = ∑_{m=1}^{N} (∑_{d|m} d·μ(m/d)) * ⌊N/m⌋²
// = ∑_{m=1}^{N} φ(m) * ⌊N/m⌋²    (т.к. ∑_{d|m} d·μ(m/d) = φ(m))

ll sum_gcd(ll N) {
    int n = (int)N;
    MultiplicativeSieve sieve(n);
    ll res = 0;
    for (int m = 1; m <= n; m++) {
        ll q = N / m;
        res += (ll)sieve.phi[m] * q * q;
    }
    return res; // ∑∑gcd(i,j) для 1≤i,j≤N
}

int main() {
    ll N = 1000;
    // Проверка: ∑_{n=1}^{10} d(n) = 1+2+2+3+2+4+2+4+3+4 = 27
    cout << "∑d(n), n≤10: " << sum_divisors_count(10) << "\n"; // 27
    // ∑φ(n), n≤10 = 1+1+2+2+4+2+6+4+6+4 = 32
    // Через решето:
    MultiplicativeSieve sieve(10);
    ll phi_sum = 0;
    for (int i = 1; i <= 10; i++) phi_sum += sieve.phi[i];
    cout << "∑φ(n), n≤10: " << phi_sum << "\n"; // 32

    // Число взаимно простых пар (a,b) с a,b≤5
    cout << "#{gcd=1, a,b≤5}: " << count_coprime_pairs(5) << "\n";

    // ∑∑gcd(i,j), i,j≤5
    ll brute_gcd = 0;
    for (int i = 1; i <= 5; i++)
        for (int j = 1; j <= 5; j++)
            brute_gcd += __gcd(i, j);
    cout << "∑∑gcd, n=5 (брутфорс): " << brute_gcd << "\n";
    cout << "∑∑gcd, n=5 (Мёбиус):   " << sum_gcd(5) << "\n";

    return 0;
}

Анализ сложности.

• sum_divisors_count(N): O(√N) — разбивка на O(√N) блоков.
• count_coprime_pairs(N): O(N) с предвычислением μ, O(N^{2/3}) с методом Люси.
• dirichlet_convolution: O(N log N).
• sum_gcd(N): O(N) — линейное решето + проход.

---

Разбор задачи 1 (средняя)

Задача. Вычислить ∑{i=1}^{N} ∑{j=1}^{N} gcd(i, j) при N ≤ 10^6.

Решение. Используем формулу выше: ∑∑gcd(i,j) = ∑_{m=1}^{N} φ(m) · ⌊N/m⌋².

int main() {
    ll N;
    cin >> N;
    cout << sum_gcd(N) << "\n"; // O(N) с линейным решетом
}

Объяснение тождества. Переписываем ∑∑gcd = ∑_d d · #{(i,j) : gcd(i,j)=d}. Замена i=da, j=db: ∑d d · #{(a,b) : gcd(a,b)=1, a,b≤N/d}. Считаем #{gcd=1, ≤K} = ∑{k|*} μ(k)⌊K/k⌋² = ∑_k μ(k)⌊K/k⌋². Подставляем и меняем порядок суммирования: ∑m (∑{d|m} d·μ(m/d)) · ⌊N/m⌋² = ∑_m φ(m)·⌊N/m⌋².

---

Разбор задачи 2 (сложная)

Задача. Дано N. Найти ∑{k=1}^{N} ∑{i=1}^{k} gcd(i, k) по модулю 10^9+7. N ≤ 10^10.

Решение. Обозначим f(k) = ∑{i=1}^{k} gcd(i,k). Тогда f(k) = ∑{d|k} d · φ(k/d) (стандартная формула через свёртку). Нам нужна ∑{k=1}^{N} f(k) = ∑{k=1}^{N} ∑_{d|k} d · φ(k/d).

Замена переменных: d · m = k, m = k/d:

∑_{k=1}^{N} f(k) = ∑_{m=1}^{N} ∑_{d=1}^{⌊N/m⌋} d · φ(m)
                  = ∑_{m=1}^{N} φ(m) · T(⌊N/m⌋)

где T(K) = ∑_{d=1}^{K} d = K(K+1)/2.

Теперь используем гиперболическое суммирование: ⌊N/m⌋ принимает O(√N) значений. Для каждого значения q = ⌊N/m⌋ суммируем φ по блоку m, где ⌊N/m⌋ = q.

Нам нужны префиксные суммы φ: P(k) = ∑_{m=1}^{k} φ(m). Но N = 10^10 — не можем создать массив размера N. Используем метод "черно-белых клеток" (Lucy's sieve) для вычисления P(k) для O(√N) значений k за O(N^{2/3}) времени.

// Метод Люси для вычисления P(k) = ∑_{m≤k} φ(m) для всех k вида ⌊N/i⌋
// За O(N^{2/3}) (набросок)
void lucy_phi(ll N) {
    ll sqrtN = (ll)sqrt((double)N);
    // small[i] = P(i) для i ≤ sqrtN
    // large[i] = P(N/i) для i ≤ sqrtN
    vector<ll> small(sqrtN + 1), large(sqrtN + 1);
    // Инициализация: P(k) = k*(k-1)/2 (если все взаимно просты — нет, это P_1)
    // ... (полная реализация см. метод Люси Бедрён)
    // После вычисления: ∑_{m≤k} φ(m) известно для всех нужных k
}

Итоговая сложность: O(N^{2/3}) — стандартное для задач такого типа.

---

Разбор задачи 3 (ICPC WF / CF Div.1 E)

Задача (CF 1033E / похожая). Дан массив из n ≤ 3·10^5 чисел a_i ≤ 10^6. Обработать q ≤ 3·10^5 запросов вида: добавить число x в массив / удалить число x / найти число пар (i, j) с gcd(a_i, a_j) = 1.

Решение. Поддерживаем cnt[d] = число элементов, кратных d. Тогда число пар с gcd кратным d = C(cnt[d], 2).

Ответ = ∑_{d=1}^{M} μ(d) · C(cnt[d], 2).

При добавлении x: нужно обновить cnt[d] для всех d | x. Число делителей d(x) в среднем O(log x), максимум O(x^ε). При обновлении cnt[d] пересчитать вклад μ(d) · (cnt[d]·(cnt[d]-1)/2) → ответ меняется на μ(d) · cnt_new[d]. Это инкрементальное обновление за O(d(x)) на каждую операцию.

const int M = 1e6 + 5;
MultiplicativeSieve sieve(M);
ll cnt[M] = {};
ll answer = 0;

// Все делители числа n
vector<int> get_divisors(int n) {
    vector<int> divs;
    for (int d = 1; (ll)d*d <= n; d++) {
        if (n % d == 0) {
            divs.push_back(d);
            if (d != n/d) divs.push_back(n/d);
        }
    }
    return divs;
}

void add(int x) {
    for (int d : get_divisors(x)) {
        answer += sieve.mu[d] * cnt[d]; // new pairs gcd divisible by d
        cnt[d]++;
    }
}

void remove_elem(int x) {
    for (int d : get_divisors(x)) {
        cnt[d]--;
        answer -= sieve.mu[d] * cnt[d]; // removed pairs
    }
}

Сложность: O((n + q) · D) где D = средний d(x) ≈ O(log x) ≈ O(20) для x ≤ 10^6.

---

Задачи для самостоятельного решения

---

Типичные ошибки

1. Формула для φ(n) через Мёбиус. φ(n) = ∑{d|n} μ(d) · (n/d), а НЕ ∑{d|n} μ(d). Путаница возникает при работе с инверсией Мёбиуса.
2. Двойной учёт в гиперболическом суммировании. При разбивке суммы по гиперболе ab ≤ N нужно вычесть "квадрат" (a ≤ √N и b ≤ √N): ∑{ab≤N} = ∑{a≤√N} (∑{b≤N/a} ...) + ∑{b≤√N} (∑{a≤N/b} ...) − ∑{a,b≤√N}.
3. Переполнение в ∑∑gcd. При N = 10^6, ∑∑gcd ≈ N² · ln N / 2 ≈ 7 · 10^12 — нужен long long.
4. Свёртка Дирихле ≠ обычная свёртка. Свёртка Дирихле: c(n) = ∑{d|n} a(d)b(n/d). Обычная (мультипликативная): c(n) = ∑{k+j=n} a(k)b(j). Это разные операции!
5. Функция Мертенса M(n) может быть отрицательной. M(n) = ∑_{k=1}^{n} μ(k) — не монотонная, может быть −10 или +5 для одного n.

---

Совет профессионала

Мёбиус инверсия — "швейцарский нож" теории чисел в CP. Паттерн использования:

Задача: подсчитать пары (i,j) с каким-то свойством P(gcd(i,j)). Решение:

1. Выразить P(d) через "простые" события (кратность d)
2. Применить инверсию Мёбиуса: P(gcd = d) = ∑_{d|k} μ(k/d) · [gcd кратно k]
3. Поменять порядок суммирования

Ключевое тождество для запоминания: ∑_{d|n} μ(d) = [n=1] (единица по Кронекеру). Отсюда: если h(n) = ∑{d|n} f(d), то f(n) = ∑{d|n} μ(n/d) h(d).

Гиперболическое суммирование работает всегда, когда нужна сумма f(⌊N/k⌋) по k — это O(√N) блоков с одинаковым значением. Эта техника появляется в задачах на подсчёт решётчатых точек, суммирование мультипликативных функций и вычислении ζ-сумм.

---

Итог

Дзета-функция Римана и теория мультипликативных функций дают мощные инструменты для анализа и вычисления. Ключевые результаты: среднее число делителей ~ ln n; среднее φ(n) ~ 6n/π²; формула Мертенса для суммы 1/p. Метод гиперболической суммации Дирихле позволяет вычислять диагональные суммы за O(√N) вместо O(N). Инверсия Мёбиуса переводит между "накопленными" и "точными" значениями мультипликативных функций. Все эти инструменты критически важны для эффективного решения задач, связанных с НОД, делителями и арифметическими суммами.