Prefix sum of integral function -- Du Jiao sieve

background ：

This class is so boring , Too noisy to learn , Just write a blog .

subject :

Given a $n$, seek ${\sum }_{i=1}^n\mu (i)$ and ${\sum }_{i=1}^n\phi (i)$.
$(1\le n\le 10^{10})$
( Prefixes and of some integrable functions )

introduction :

If you don't know what an integral function is, go out and turn left Next door classroom .

We know ,$\mu$ Functions and $\phi$ Sure $o(\sqrt{n})$ Find the value of a single point .
You can also use a linear sieve $o(n)$ Preprocess the values of multiple points .
But obviously it's not enough for this problem .

Come to such a magical place , These integrable functions have a sub linear algorithm to find the prefix and , Maybe this is the charm of Mathematics .
Here we introduce one of the methods , Dujiao sieve , It can be $o(n^{\frac{3}{4}})$ Find the prefix and sum of the integral function within the complexity of . And we can preprocess it out before $10^6$ Two prefixes and , Optimize its complexity to $o(n^{\frac{2}{3}})$.

Text ： Dujiao sieve

Suppose that the function we require the prefix and is $f$, And make its prefix and $S(n)={\sum }_{i=1}^{n}f(i)$.
Let's find another function $g$ Convolute with it to find the prefix sum .
${\sum }_{i=1}^n(f\ast g)(i)={\sum }_{i=1}^n{\sum }_{d|i}g(d)f(\frac{i}{d})$

                             $={\sum }_{d=1}^{n}g(d){\sum }_{i=1}^{\lfloor \frac{n}{d}\rfloor }f(i)$

                             $={\sum }_{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

Push it here , We find that this is an obvious number theory block formula .
But there is no in this formula $S(n)$ ah , no $S(n)$ What are we asking for .
So now we're going to $S(n)$ Get it out .
We found that when $d=1$ when , This thing in the back $g(1)S(\lfloor \frac{n}{1}\rfloor )=S(n)$
then $S(n)$ came .
$S(n)={\sum }_{d=1}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )-{\sum }_{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

          $={\sum }_{i=1}^n(f\ast g)(i)-{\sum }_{d=2}^{n}g(d)S(\lfloor \frac{n}{d}\rfloor )$

Then the latter formula is still a number theory block formula , As long as we can quickly find $g$ And , You can quickly find out .

So we need to find one $g$, bring $g$ and $f\ast g$ The prefix and are easy to find .

Let's now calculate the complexity , hypothesis $g$ and $f\ast g$ The prefix and can $o(1)$ Find out .
So there are . Excuse me , Anyway, the complexity is $o(n^{\frac{3}{4}})$, If we preprocess out before $10^6$ term , Then add a memory , Complexity becomes $o(n^{\frac{2}{3}})$ 了 .

The code is omitted , Please write your own questions .

Example 1： seek ${\sum }_{i=1}^n\mu (i)$.

When we consider solving the prefix sum of integral functions with Duchenne sieve , The main thing is to find one $g$ bring $g$ and $f\ast g$ Prefix and easy to find .
So for the Mobius function $\mu$, There is no doubt that we choose to use $1$ function .
Yes $\mu \ast 1=e$.
that $1$ Functions and $e$ There is no need to say more about the prefix and sum of functions .
The reason is A.

Example 2： seek ${\sum }_{i=1}^n\phi (i)$.

$g$ Still choose to use $1$ function , Yes $\phi \ast 1=id$.
that $1$ Functions and $id$ The prefix summation function is also very good .

Example 3： seek ${\sum }_{i=1}^{n}i\phi (i)$.

We chose to use $id$ As $g$ function , First $id$ The prefix and sum of functions can be found .
${\sum }_{i=1}^n(f\ast id)(i)={\sum }_{i=1}^n{\sum }_{d|i}d\phi (d)\ast \frac{i}{d}={\sum }_{i=1}^{n}i{\sum }_{d|i}\phi (d)={\sum }_{i=1}^n{i}^2$.
among , because $1\ast \phi =id$, therefore ${\sum }_{d|i}\phi (d)=i$.

Example n+2： seek ${\sum }_{i=1}^n{i}^n\phi (i)$.

We chose to use $i{d}^n$ As $g$ function , that $i{d}^n$ The prefix and sum of can be found .（ Lagrange interpolation ?）
${\sum }_{i=1}^n(f\ast id)(i)={\sum }_{i=1}^n{\sum }_{d|i}{d}^n\phi (d)\ast (\frac{i}{d}{)}^n={\sum }_{i=1}^n{i}^n{\sum }_{d|i}\phi (d)={\sum }_{i=1}^n{i}^{n+1}$.

For the time being, I know that's all above .