Метод гиперболы Дирихле — используемая в теории чисел техника вычисления суммы вида , где — мультипликативная функция, представимая в виде свёртки Дирихле, .
В таком случае, используя комбинаторный принцип включений-исключений, сумму можно переписать в следующем виде: . Такая форма записи удобна как для теоретической оценки асимптотики суммирующей функции , так и для более быстрого точного её вычисления в случае, если возможно быстро вычислять и их суммирующие функции.
Пример Рассмотрим суммирующую функцию делителей
где — количество делителей . Поскольку , выбрав , получаем
что позволяет найти за операций, что значительно быстрее, чем использование, например, решета Эратосфена.
Кроме того, полученная формула помогает оценить асимптотику суммирующей функции :
где — постоянная Эйлера — Маскерони.
Примечания
Ссылки Summing Multiplicative Functions, griff's math blog Dirichlet convolution. Part 1: Fast prefix sum computations, codeforces
Категория:Теория чисел Категория:Арифметические функции