Dirichlet 前缀和（数论优化式子复杂度利器）

概述

当式子优化到${\sum }_{d=1}^n{\sum }_{d|i}s(i)$类似形式时，我们可以$o(nlogn)$做。但是当$n$取$10^7$时就十分危险了，直到今天发现了这么个东西——Dirichlet 前缀和。它可以在$o(nloglogn)$的复杂度内解决这个问题，快近似$o(n)$了。
这篇博客用来记板子，要学可以看这篇博客。

Dirichlet 前缀和

式子：（给定$a$，求$b$）

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

代码：

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 后缀和

式子：（给定$a$，求$b$）

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

代码：

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

倒推Dirichlet 前缀和

式子：（给定$b$，求$a$）

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

代码：

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

倒推Dirichlet 后缀和

式子：（给定$b$，求$a$）

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

代码：

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

附录（配套素数筛）

代码：

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