Dirichlet prefix sum (number theory optimization formula sub complexity weapon)

summary

When the formula is optimized to ${\sum }_{d=1}^n{\sum }_{d|i}s(i)$ In a similar form , We can $o(nlogn)$ do . But when $n$ take $10^7$ It's very dangerous when , Until today, I found such a thing ——Dirichlet The prefix and . It can be $o(nloglogn)$ Solve this problem within the complexity of , Fast approximation $o(n)$ 了 .
This blog is used to write down the board , To learn, you can see This blog .

Dirichlet The prefix and

Formula ：（ Given $a$, seek $b$）

$$b[d]=\sum _{i|d}a[i]$$

Code ：

for(int i=0;i<tot&&prime[i]<=n;i++)
{
    
     for(int j=1;j*prime[i]<=n;j++)
     {
    
         a[j*prime[i]]+=a[j];
     }
 }

Dirichlet Suffixes and

Formula ：（ Given $a$, seek $b$）

$$b[d]=\sum _{d|i}a[i]$$

Code ：

for(int i=0;i<tot&&prime[i]<=n;i++)
{
    
     for(int j=n/prime[i];j;j--)
     {
    
         a[j]+=a[j*prime[i]];
     }
 }

Push backward Dirichlet The prefix and

Formula ：（ Given $b$, seek $a$）

$$b[d]=\sum _{i|d}a[i]$$

Code ：

for(int i=tot-1;i>=0;i--)
{
    
    for(int j=n/prime[i];j;j--)
    {
    
        a[j*prime[i]]-=a[j];
    }
}

Push backward Dirichlet Suffixes and

Formula ：（ Given $b$, seek $a$）

$$b[d]=\sum _{d|i}a[i]$$

Code ：

for(int i=tot-1;i>=0;i--)
{
    
    for(int j=1;j*prime[i]<=n;++j)
    {
    
        a[j]-=a[j*prime[i]];
    }
}  

appendix （ Matching prime sieve ）

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;
        }
    }
}