Dirichlet求和_牛客博客

$b_i=\sum_{d|i}a_d$
求出 $b_i$ 的话一般是 $n\log n$ 的复杂度。
可以转移质因子的贡献，优化到 $n\log \log n$ 的复杂度。

前缀和

$b_i=\sum_{d|i}a_d$
知道 $a_i$ 求 $b_i$

for(int i=1;i<=cnt&&pri[i]<=n;i++){
    for(int j=1;j*pri[i]<=n;i++){
        a[j * pri[i]] += a[j];
    }
}

知道 $b_i$ 求 $a_i$

    for(int i = cnt; i ; -- i) {
        for(int j = n / pri[i]; j ; -- j) {
            a[j * pri[i]] -= a[j];
        }
    }

后缀和

$b_d=\sum_{d|i}a_i$
知道 $a_i$ 求 $b_i$

    for(int i = 1; i <= cnt && pri[i] <= n; ++ i) {
        for(int j = n / pri[i]; j ; -- j) {
            a[j] += a[j * pri[i]];
        }
    }

知道 $b_i$ 求 $a_i$

    for(int i = cnt; i ; -- i) {
        for(int j = 1; j * pri[i] <= n; ++ j) {
            a[j] -= a[j * pri[i]];
        }
    }

例题

题目链接
$Description$
$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\varphi(ij)\mu(ij)$
$Solution$

$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)\varphi(ij)\mu(ij) \\=\sum_{i=1}^{n}\varphi(i)\mu(i)\sum_{j=1}^{m}\varphi(j)\mu(j)[gcd(i,j)=1] \\=\sum_{d=1}^{n}\mu(d)\sum_{d|i,i\le n}\varphi(i)\mu(i)\sum_{d|j,j\le m}\varphi(j)\mu(j)$

可以用 $Dirichlet$ 后缀和求出 $\sum_{d|i,i\le n}\varphi(i)\mu(i)$

$Code$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in","r",stdin);
#define OUT freopen("out","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=2e7+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
typedef unsigned int uint;
uint phi[N];
int cnt=0,pri[N];
bool vis[N];
uint mu[N];
uint s[N],t[N];
void pre(){
    phi[1]=1;
    mu[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i])pri[++cnt]=i,phi[i]=i-1,mu[i]=-1;
        for(int j=1;j<=cnt&&i*pri[j]<N;j++){
            vis[i*pri[j]]=true;
            if(i%pri[j]==0){
                phi[i*pri[j]]=phi[i]*pri[j];
                mu[i*pri[j]]=0;
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
            mu[i*pri[j]]=-mu[i];
        }
    }
}
int main(){
    pre();
    int tt;cin>>tt;
    while(tt--){
        int n,m;
        sc("%d%d",&n,&m);
        for(int i=1;i<=n;i++)s[i]=phi[i]*mu[i];
        for(int i=1;i<=m;i++)t[i]=phi[i]*mu[i];
        for(int i=1;pri[i]<=n||pri[i]<=m;i++){
            if(pri[i]<=n)for(int j=n/pri[i];j;j--)s[j]+=s[j*pri[i]];
            if(pri[i]<=m)for(int j=m/pri[i];j;j--)t[j]+=t[j*pri[i]];
        }
        uint ans=0;
        for(int d=1;d<=min(n,m);d++){
            ans+=mu[d]*s[d]*t[d];
        }
        pr("%u\n",ans);
    }
}