Метод гиперболы Дирихле

Метод гиперболы Дирихле — используемая в теории чисел техника вычисления суммы вида

${\displaystyle F(x)=\sum _{n\leqslant x}f(n)}$,

где ${\displaystyle f}$ — мультипликативная функция, представимая в виде свёртки Дирихле, ${\displaystyle f=g*h}$.

В таком случае, используя комбинаторный принцип включений-исключений, сумму можно переписать в следующем виде:

${\displaystyle F(x)=\sum _{n\leqslant x}f(n)=\sum _{n\leqslant x}\sum _{ab=n}g(a)h(b)=\sum _{a\leqslant {\sqrt {x}}}\sum _{b\leqslant {\frac {x}{a}}}g(a)h(b)+\sum _{b\leqslant {\sqrt {x}}}\sum _{a\leqslant {\frac {x}{b}}}g(a)h(b)-\sum _{a\leqslant {\sqrt {x}}}\sum _{b\leqslant {\sqrt {x}}}g(a)h(b)}$.

Такая форма записи удобна как для теоретической оценки асимптотики суммирующей функции ${\displaystyle F(x)}$, так и для более быстрого точного её вычисления в случае, если возможно быстро вычислять ${\displaystyle g,h}$ и их суммирующие функции.

Рассмотрим суммирующую функцию делителей

${\displaystyle D(n)=\sum _{k=1}^{n}\tau (k),}$

где ${\displaystyle \tau (k)}$ — количество делителей ${\displaystyle k}$. Поскольку ${\displaystyle \tau =1*1}$, выбрав ${\displaystyle a=b={\sqrt {n}}}$, получаем

${\displaystyle D(n)=\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{n/x}1\cdot 1+\sum _{y=1}^{\sqrt {n}}\sum _{x=1}^{n/y}1\cdot 1-\sum _{x=1}^{\sqrt {n}}\sum _{y=1}^{\sqrt {n}}1\cdot 1=2\cdot \sum _{x=1}^{\sqrt {n}}\left\lfloor {\frac {n}{x}}\right\rfloor -\left\lfloor {\sqrt {n}}\right\rfloor ^{2},}$

что позволяет найти ${\displaystyle D(n)}$ за ${\displaystyle O({\sqrt {n}})}$ операций, что значительно быстрее, чем использование, например, решета Эратосфена.

Кроме того, полученная формула помогает оценить асимптотику суммирующей функции^[1][2]:

${\displaystyle D(n)=n\log n+(2\gamma -1)n+O({\sqrt {n}}),}$

где ${\displaystyle \gamma }$ — постоянная Эйлера — Маскерони.

• Summing Multiplicative Functions, griff's math blog
• Dirichlet convolution. Part 1: Fast prefix sum computations, codeforces