Integral function and Dirichlet convolution

Preface ：

Early to bed and early to rise makes a man healthy,wealthy and wise. ！ Today, let's talk about the integral function .
 

Definition of product function ：

What is an integral function ？（ Also called multiplicative function ）
 
Let's start with a broader concept , Arithmetic functions .（ Arithmetic function Number theoretic functions ）
Arithmetic functions , Is a function defined for all positive integers , That is, a function whose domain is a positive integer .
 
and Integrability function , Is a special arithmetic function .
 
For the function $f(x)$,
If meet $f(1)=1$,
And for any coprime positive integer $p$ and $q$, Satisfy $f(pq)=f(p)f(q)$,
said $f(x)$ It's a product function .
 
And for functions $f(x)$,
If meet $f(1)=1$,
And for any positive integer $p$ and $q$, Satisfy $f(pq)=f(p)f(q)$,
said $f(x)$ Is a completely integrable function .
（ That's not what we're talking about here ）
 
Let's focus on the integral function , Now let's move on to this definition .
According to the unique decomposition theorem , We can $x$ Decompose to get $x=p_1^{k_1}{p}_2^{k_2}\dots p_n^{k_n}$.
Then there are $f(x)=f(p_1^{k_1})f(p_2^{k_2})\dots f(p_n^{k_n})$.
in other words , When we want to define an integral function , We just need to define the power of prime numbers , Then the function values of all numbers have been obtained .
 
Now? , We can pinch out a useless integral function by ourselves .
We define $f(x)=\{\begin{array}{ll}1& \text{,}x=1\\ p\times k& \text{,}x=p^k,pyesqualityCount,kyesjustwholeCount\end{array}$
Then explain when $a\perp b$ when ,$f(ab)=f(a)f(b)$ that will do .（$a\perp b$ Express $a$ And $b$ Coprime ）
It's useless to pinch the product function .
 
 
 

Common product function ：

Now let's talk about some useful integral functions .

Unit function and constant function ：

Let's start with two obvious integrable functions .
 
The first is Unit function $e(n)=[n=1]$,
（ brackets $[]$ Represents a logical operation , When the expression in parentheses holds , Then the value is $1$, Instead of $0$）
in other words , When $x=1$ when ,$e(x)=1$; When $x\ne 1$ when ,$e(x)=0$.
It can be understood as unit element , There will be a deeper understanding later .
 
The second is Constant function $1(n)=1$.
Cough , The first one here $1$ Is a function symbol , Don't ask me why I said that .
The function is , For arbitrary $x$, All meet $1(x)=1$.
 
Of course, these two functions are completely integrated functions , This is not the point , We continue .
 

Euler function $\phi (n)$：

Euler function $\phi (n)$, Less than or equal to $n$ And with the $n$ The number of Coprime numbers .
For example, less than or equal to $6$, and $6$ The number of Coprime is $1$ and $5$, therefore $\phi (6)=2$.
 
This function is more useful , I want to open a separate blog about , Here's just Prove that it is an integral function .
Because I can't prove , So here's a circular argument .
Let's just remember that it's an integral function , The hole left will be filled in when we talk about it .
One point ,$\phi (p^k)=p^k-p^{k-1}$, among $p$ Prime number ,$k$ It's a positive integer. .
 

The sum of factors and the number of factors ：

Factors and functions $\sigma (n)$, Express $n$ The factor and , Yes $\sigma (n)={\sum }_{d|n}d$.
Factor number function $\tau (n)$, Express $n$ The factor and , Yes $\tau (n)={\sum }_{d|n}1$.
Prove that these two are integral functions , If you are interested, you can prove yourself .
here ${\sum }_{d|n}$ It's enumeration $n$ All the factors of $d$.
It's also clear from the formula . The sum of factors is to enumerate all factors $d$, Then put all the factors $d$ Add up . The number of factors is to enumerate all the factors , Then add one for each factor $1$.
 
Give me the same ,
$\sigma (p^k)=1+p+p^2+\dots +p^k=\frac{p^{k+1}-1}{p-1}$,
$\tau (p^k)=k+1$,
Both of them are easier to get out .
 

Mobius function $\mu (n)$：

It's another function of the great God level , It's also a separate article , Let's start with the definition .
$\mu (n)=\{\begin{array}{ll}1& \text{,}x=1\\ (-1{)}^r& \text{,}x=p_1{p}_2\dots p_r,namelyxOftheYesplainbecauseSonTimeCountallby1,ItsinrsurfaceinplainbecauseSonindividualCount\\ 0& \text{,}ItsHeloveshape,namelyxsavestayflatFangbecauseSon\end{array}$
 
This definition is outrageous , I'll talk about its origin later .
Now it's the same, as long as you know that it's an integral function .
 
 

Integral function sieve ：

You need to know something , All integrable functions are OK $o(n)$ Sifted out .
（ Of course , When you just need to find the value of a function , Yes, there can be almost $o(\sqrt{n})$ The practice of getting faster , And screening is screening out $1$ To $n$ The value of the integral function of ）
 
So how to screen ？
First , The integral function sieve is based on $o(n)$ Based on the prime sieve .

Let's start with the linear prime sieve .
Linear prime sieve is improved on the basis of Egyptian sieve —— Let each number be sifted out by only one number .
We know , The Angstrom sieve uses every prime number , To sift its multiples . And the linear sieve , Make sure that each number is only screened out by its smallest prime factor .
Go straight to the code .

int notPrime[MAXN],prime[MAXN],tot;
void getPrime(int n)
{
    
    notPrime[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j]==0)break;
        }
    }
}

Explain the principle of this code .
First , All composite numbers can be expressed as another number multiplied by its minimum prime factor .
So when we get a number , Just enumerate which prime number is selected as its minimum prime factor .
So this code , First, enumerate each number $i$, If not screened , Then throw it to the prime list $prime[]$ in .
Then for this number $i$, One more thing we have to do , Is to enumerate the smallest prime factor it multiplies $prime[j]$.
When $i$ The number of , Can divide the current prime factor , Then you can't enumerate later . Because the current factor is $i$ A prime factor of , If we enumerate later , It's bigger than this prime factor , Then it's not sifted by the smallest prime factor .
That's where the code ends .
 
 
Now let's talk about the sieve of integral functions .
In fact, it is an improvement on the basis of prime sieve .
First , For integrable functions $f(x)$, We need to be able to quickly calculate $f(p^k)$ The ability of , Just as we said in the previous definition , Then according to the properties of the integral function , Get other function values .
When it's done , We calculate the value of the integral function of each number at the position where it is screened out $f(x)$.
First , When sifting out prime numbers , Let's just take the prime number p Function value of $f(p)$ Fu Shang .
Then when you sift the numbers in the cycle , There are two situations , One is $i$ Can not be $prime[j]$ Divisible , Then there is $gcd(i,prime[j])=1$ establish , obtain $f(i\times prime[j])=f(i)f(prime[j])$.
Then there is only one last case , Namely $i$ Can be $prime[j]$ The condition of division , At this time, we deal with $i$ The power of the smallest prime factor in $lo{w}_i$, There is $gcd(\frac{i}{lo{w}_i},prime[j]\times lo{w}_i)$, You can get $f(i\times prime[j])=f(\frac{i}{lo{w}_i})f(prime[j]\times lo{w}_i)$.
Last , Find a way to deal with $lo{w}_i$ Just fine , This can also be handled during screening . Because we sift with the smallest prime factor , So there is $low(i\times prime[j])=low(i)\times prime[j]$.
Come here , And it's done .
Upper template .（ This board is written now , There may be no problem ）

int notPrime[MAXN],prime[MAXN],tot,low[MAXN];
int f[MAXN];
void getFunc(int n)
{
    
    notPrime[1]=f[1]=low[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])low[i]=prime[tot++]=i,f[i]=( Prime numbers are calculated directly );
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])
            {
    
                low[i*prime[j]]=prime[j];
                f[i*prime[j]]=f[i]*f[prime[j]];
            }
            else 
            {
    
                low[i*prime[j]]=low[i]*prime[j];
                if(low[i]==i)f[i*prime[j]]=( Direct calculation of prime power );
                else f[i*prime[j]]=f[i/low[i]]*f[prime[j]*low[i]];
                break;
            }
        }
    }
}

 
 
The above is the general solution of integral function .
Now let's talk about special , Sieve method of Euler function and Mobius function .
The principle is the same , But there are some convenient places .
 
Let's start with Mobius function .
First, prime numbers $p$ Function value of $\mu (p)=-1$.
So when $i$ Don't be $p$ Divisible time , It's the same as seeking the law , Directly use the properties of integral function ,$\mu (ip)=\mu (i)\mu (p)=-\mu (i)$.
When $i$ By $p$ Divisible time ,（ We know , When $x$ When there is a square factor ,$\mu (x)=0$）, You can boldly give $0$ 了 .
Templates ：

int notPrime[MAXN],prime[MAXN],tot;
int mu[MAXN];
void initMu(int n)
{
    
    notPrime[1]=mu[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,mu[i]=-1;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])mu[i*prime[j]]=-mu[i];
            else {
    mu[i*prime[j]]=0;break;}
        }
    }
}

 
Then there's the Euler function ,
Prime time ,$\phi (p)=p-1$.
Then it has a magical property , For a prime number $p$, if $p|i$, be $\phi (ip)=\phi (i)p$; if $p$ Not divisible $i$, be $\phi (ip)=\phi (i)(p-1)$.
And then according to this , It is also easy to write Euler functions .

int notPrime[MAXN],prime[MAXN],tot;
int phi[MAXN];
void initPhi(int n)
{
    
    notPrime[1]=phi[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!notPrime[i])prime[tot++]=i,phi[i]=i-1;
        for(int j=0;j<tot&&i*prime[j]<=n;j++)
        {
    
            notPrime[i*prime[j]]=1;
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);
            else {
    phi[i*prime[j]]=phi[i]*prime[j];break;}
        }
    }
}

 
The product function sieve is finished .
 
 

Dirichlet ：

Before we talk about it , Give a few more number theoretic functions .（ Pay attention to the difference between number theoretic function and integral function ）
$id(n)=n$, Represents its own function , The function value is equal to the argument itself .
$\omega (n)={\sum }_{p|n}1$, among $p$ Prime number , The function value represents $n$ The number of prime factors of .
 
 
Let's talk. Let's talk .
Dirichlet convolution operation is an important algorithm of number theory function .
Yes , It's an algorithm , Like addition, subtraction, multiplication and division .
And it's the algorithm of the function , The result of the operation is also a function .
You can think of it this way , This is an operation mechanism specially established for number theory functions .
 
We will number theoretic functions $f$ And number theoretic functions $g$, After Dirichlet convolution , Get a new number theoretic function $h=f\ast g$.（ there $\ast$ Not a multiplication sign , It's the sign of convolution ）
So what's the algorithm .
That's the definition of convolution $h(n)=(f\ast g)(n)={\sum }_{d|n}f(d)g(\frac{n}{d})={\sum }_{d|n}f(\frac{n}{d})g(d)$.
 
Now let's look at this formula ,${\sum }_{d|n}$ It should be no stranger , Is enumerating factors .
Let's go back to the previous two formulas .
Number of factors $\tau (n)={\sum }_{d|n}1$, We find that this function is actually obtained by convolution of two constant functions .
We get a formula $\tau =1\ast 1$.
So in the same way , Look at the factors and $\sigma (n)={\sum }_{d|n}d$, And then there is $\sigma =1\ast id$.

Come here , Convolution operation should be simple to understand .
Also know Some properties of Dirichlet convolution operation .
First , it Satisfying the commutative law , Associative law .
then , For any number theoretic function $f$, Yes $f\ast e=f$, That is, the unit function is a unit element .
also , if $f$ It's a product function , And $g$ It's a product function , be $f\ast g$ It's also a product function .

Convolution is probably like this .
Now List the convolution relations between some functions .
$\tau =1\ast 1$
$\sigma =1\ast id$
$1\ast \mu =e$
$\phi \ast 1=id$
$\phi =id\ast \mu$
 
The first two formulas have been mentioned earlier , I won't talk about it .
 
You will find that the third formula is a magical formula , The constant function on the Mobius function volume is actually a unit element , let me put it another way ,$\mu$ and $1$ It's the opposite of each other .
In fact, this is a pit buried in front of us , On the deviant definition of Mobius function .
You can understand , It is used to construct the inverse of a constant function , In this way, Mobius inversion can be realized , The blog in the next chapter will talk about .
thus , You can also get some more formulas , for example $\tau \ast \mu =1$,$\sigma \ast \mu =id$ wait , That is, multiply both sides of the equation by $\mu$ And $1$ Offset .
 
Let's look at the last two formulas , It's actually the same formula , According to the front $1$ and $\mu$ The inverse element relation of .
As for why $\phi =id\ast \mu$, This formula is very important , I'll talk about it later in Mobius inversion .
 
 
 
This lesson is too big 6000 word , Hard top , It's over .