狄利克雷

标签：frac log 狄利克 int sum ln zeta

一大堆带着 Dirichlet 的东西。原计划是整点拉格朗日反演，但是看见 jijidawang 博客给我来劲了，遂改。

Dirichlet 前缀和

给你一个函数（或者数列） \(f\)，然后让你求 \(g_n=\sum_{d|n}f_d\) 在 \(1-n\) 的所有取值。其实就是卷个 \(I\)。

当然可以枚举倍数做到 \(O(n\log n)\)。但是不够优秀。

实际上把每个质因数当成一维，然后做高维前缀和就行了。代码就这点。

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

复杂度 \(O(n\log\log n)\)。

类似的有 Dirichlet 差分（就是卷 \(\mu\)）：

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

同样有后缀和（枚举倍数求和）以及后缀差分：

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

P2714 四元组统计

基础应用。对于 \(\gcd(a_i,a_j,a_k,a_l)=x\) 的，先做个 Dirichlet 后缀和，此时所有 \(x\) 的位置变成了 \(x\) 的倍数个数，然后把 \(a_x\) 变成 \(\binom {a_x}4\) ，最后 Dirichlet 后缀差分回去就可以了。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define int long long
using namespace std;
int n,a[10010],p[10010];
bool v[10010];
void get(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])p[++p[0]]=i;
        for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
            v[i*p[j]]=true;
            if(i%p[j]==0)break;
        }
    }
}
signed main(){
    get(10000);
    while(~scanf("%lld",&n)){
        int mx=0;
        for(int i=1;i<=n;i++){
            int x;scanf("%lld",&x);a[x]++;
            mx=max(mx,x);
        }
        for(int i=1;i<=p[0];i++){
            for(int j=mx/p[i];j;j--){
                a[j]+=a[p[i]*j];
            }
        }
        for(int i=1;i<=mx;i++)a[i]=1ll*(a[i]-3)*(a[i]-2)*(a[i]-1)*a[i]/24;
        for(int i=1;i<=p[0];i++){
            for(int j=1;j*p[i]<=mx;j++){
                a[j]-=a[p[i]*j];
            }
        }
        printf("%lld\n",a[1]);
        for(int i=1;i<=mx;i++)a[i]=0;
    }
    return 0;
}

gcd/lcm 卷积

\(\gcd\) 卷积就是这个东西：

\[h_n=\sum_{\gcd(i,j)=n}f_ig_j \]

怎么算？其实可以类似地构造 DFT 和 IDFT。事实上，我们有：

\[\begin{aligned} \sum_{n|d}h_d=&\sum_{n|\gcd(i,j)}f_ig_j\\ =&\sum_{n|i,n|j}f_ig_j\\ =&\sum_{n|i}f_i\sum_{n|j}g_j \end{aligned} \]

也就是后缀和。那么做一遍高维后缀和，对应点乘，然后后缀差分回去就行了。

同样的，\(\text{lcm}\) 卷积也有：

\[\begin{aligned} \sum_{d|n}h_d=&\sum_{d|\text{lcm}(i,j)}f_ig_j\\ =&\sum_{d|i}f_i\sum_{d|j}g_j \end{aligned} \]

复杂度 \(O(n\log\log n)\)。讲道理我一开始看见的时候还挺震撼的，后来发现不是什么新东西了。

狄利克雷生成函数

是这个形式：

\[F(x)=\sum_{i=1}\frac{f_i}{i^x} \]

看起来很奇怪，\(x\) 在指数上。但是是为了满足如下性质：对于积性函数 \(f\) ，其狄利克雷生成函数可以表示为质数幂处取值的乘积：

\[F(x)=\prod_p\sum_{k=0}\frac{f(p^k)}{p^{kx}} \]

这就比较优美。

下面是一些常见数论函数的狄利克雷生成函数：

1. \(\epsilon(n)=[n=1]\)
   显然是 \(1\)。这也是狄利克雷生成函数的单位元。
2. \(\zeta(n)=1\)
   也就是 \(I\)。它是

\[\sum_{n=1}\frac 1{n^x} \]

换成质数幂处乘积的形式也就是

\[\prod_p\frac 1{1-p^{-x}} \]

3. \(\mu\)
   这个在质数幂处乘积表示下，\(k=0\) 时为 \(1\),\(k=1\) 时为 \(-1\) ，其他为 \(0\)，也就是

\[\prod_p1-p^{-x} \]

黎曼 \(\zeta\) 函数的倒数。

4. \(\text{id}_k(n)=n^k\)

\[\sum_{n=1}\frac 1{n^{x-k}} \]

显然是 \(\zeta(z-k)\)。
5. \(\varphi\)
仍然观察质数幂处取值：

\[\prod_p(1+\frac {p-1}{p^x}+\frac{p(p-1)}{p^{2x}}+\frac{p^2(p-1)}{p^{3x}}+\cdots)=\prod_p\frac{1-x^{-x}}{1-p^{1-x}}=\frac{\zeta(x-1)}{\zeta(x)} \]

6. \(\sigma_k(n)=\sum_{d|n}d^l\)
   卷积一下，是 \(\zeta(x-k)\zeta(x)\)。

一个应用：筛 \(\varphi *\mu\)。

显然是 \(\frac{\zeta(z-1)}{\zeta^2(z)}\)。拆开狄利克雷生成函数的一项：

\[\frac{(1-p^{-z})^2}{1-p^{1-z}} \]

就是幂函数的二阶差分，也就是

\[f(p^k)= \begin{cases} 1\qquad&(k=0)\\ p-2\qquad&(k=1)\\ (p-1)^2p^{k-2}\qquad&(k\ge 2) \end{cases} \]

运算

首先是卷积。一般枚举倍数，\(O(n\log n)\)。

假如说我们把 \(f\) 和 \(g\) 卷起来，\(f\) 积性。一个加速的方法是把 \(f\) 分解成 \(\pi(n)\) 个只和素数 \(p\) 有关的函数的卷积，即 \(f(x)=\prod_pf_p(x)\)。

然后把每个函数分别卷到 \(g\) 上去，那么显然

\[f_p*g(n)=\sum_{p^k|n}f(p^k)g(\frac n{p^k}) \]

那么这就是 \(O(n\log\log n)\) 的了，不算求 \(f\) 的复杂度。

然后是求逆。假设 \(f_1=g_1=1\)，\(f*g=\epsilon\)，给定 \(g\)，求 \(f\)。

\[\begin{aligned} &\sum_{d|n}f(d)g(\frac nd)=0\\ &f(n)=-\sum_{d|n,d\neq n}f(d)g(\frac nd)\\ \end{aligned} \]

当然也可以按照上边的方法 \(O(n\log\log n)\) 卷积求解。

导数和积分。单项求导试试看：

\[\left(\frac{f_n}{n^x}\right)'=-\ln n\frac{f_n}{n^x} \]

啊这，\(\ln n\) 不是有理数。所以我们换个定义。

一般的定义是把系数 \(-\ln n\) 变成 \(n\) 的可重质因子个数。积分就是逆运算。这样定义就可以满足 \(\ln ab=\ln a+\ln b\) 的关键性质。

对数和指数。对数仍然定义为

\[\ln F(x)=\int \frac{F'(x)}{F(x)}\text dx \]

然后是指数。设 \(G(x)=\exp F(x)\)，则 \(F(x)=\ln G(x)=\int \frac{G'(x)}{G(x)}\text dx\)，于是：

\[F'(x)G(x)=G'(x) \]

这玩意其实可以直接算了。

下面的代码是loj6713的，是狄利克雷快速幂。

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int mod=998244353;
int n,k,g[1000010],f[1000010];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int p[1000010],cnt[1000010];
bool v[1000010];
void get(int n){
    for(int i=2;i<=n;i++){
        if(!v[i])p[++p[0]]=i,cnt[i]=1;
        for(int j=1;j<=p[0]&&i*p[j]<=n;j++){
            v[i*p[j]]=true;
            cnt[i*p[j]]=cnt[i]+1;
            if(i%p[j]==0)break;
        }
    }
}
void div(int f[],int g[],int n){
    int inv=qpow(g[1],mod-2);
    for(int i=1;i<=n;i++){
        f[i]=1ll*inv*f[i]%mod;
        for(int j=2;i*j<=n;j++){
            f[i*j]=(f[i*j]-1ll*f[i]*g[j]%mod+mod)%mod;
        }
    }
}
void dao(int f[],int n){
    for(int i=1;i<=n;i++)f[i]=1ll*cnt[i]*f[i]%mod;
}
void jifen(int f[],int n){
    for(int i=1;i<=n;i++)f[i]=1ll*qpow(cnt[i],mod-2)*f[i]%mod;
}
void getln(int f[],int g[],int n){
    for(int i=1;i<=n;i++)g[i]=1ll*cnt[i]*f[i]%mod;
    div(g,f,n);
    jifen(g,n);
}
void exp(int f[],int g[],int n){
    g[1]=1;
    for(int i=1;i<=n;i++){
        if(cnt[i])g[i]=1ll*qpow(cnt[i],mod-2)*g[i]%mod;
        for(int j=2;i*j<=n;j++){
            g[i*j]=(g[i*j]+1ll*f[j]*cnt[j]%mod*g[i])%mod;
        }
    }
}
int main(){
    scanf("%d%d",&n,&k);
    get(n);
    for(int i=1;i<=n;i++)scanf("%d",&f[i]);
    getln(f,g,n);int inv=qpow(k,mod-2);
    for(int i=1;i<=n;i++)g[i]=1ll*g[i]*inv%mod,f[i]=0;
    exp(g,f,n);
    for(int i=1;i<=n;i++)printf("%d ",f[i]);
    printf("\n");
    return 0;
}

标签：frac,log,狄利克,int,sum,ln,zeta
From： https://www.cnblogs.com/gtm1514/p/17077221.html