数论学习笔记2：数论函数

积性函数

定义

积性函数是满足 \(\forall u\perp v,f(uv)=f(u)f(v)\) 的数论函数，\(f(1)\) 总是等于 \(1\)。

求值

由定义可知，积性函数在全体正整数处的取值由其在 \(p^k\) 处的取值完全确定。如果我们要求 \(f(n)\) 在 \(n\in[1,N]\) 处的值，首先要能够快速的求出 \(f(p^k)\) 的值，一般来说这是 \(O(1)\) 的，接下来，我们考虑欧拉筛，在欧拉筛的过程中求出生成函数，时间复杂度 \(O(n)\)：
设 \(n=\displaystyle{\prod p_i^{\alpha_i}}\)，记 \(g_n=p_1^{\alpha_1},d_n=p_1,h_n=\alpha_1\)，则有

\[f(n)=\begin{cases} f(\frac{n}{g_n})f(g_n) & n\ne g_n\\ f(d_n^{h_n}) & \text{otherwise} \end{cases} \]

int f[M], pr[M]; 
int g[M], d[M], h[M];
bool npr[M];
int calculate_f(int p, int k); // f(p^k)
...
for (int i = 2; i < M; i++) {
    if (!npr[i]) f[i] = calculate_f(i, 1), pr[++pr[0]] = i;
    for (int j = 1; j <= pr[0] && i * pr[j] < M; j++) {
        d[i * pr[j]] = pr[j];
        if (i % pr[j]) 
            g[i * pr[j]] = pr[j],
            h[i * pr[j]] = 1;
        else {
            g[i * pr[j]] = g[i] * pr[j];
            h[i * pr[j]] = h[i] + 1;
            break;
        }
    }
}
f[1] = 1;
for (int i = 2; i < M; i++)
    f[i] = g[i] == i ? calculate_f(d[i], h[i]) : f[i / g[i]] * f[g[i]];

迪利克雷卷积

定义

\[(f*g)(n)=\sum_{d|n}f(d)g(n/d) \]

性质

\[\begin{align*} &f*g=g*f\\ &f*g*h=f*(g*h)\\ &f*(g+h)=f*g+f*h\\ &\cdots\\ &\textbf{identity element}:\epsilon(n)=[n=1]\\ &\forall f,s.t.f(1)\ne 0,\exists g,s.t.f*g=\epsilon\\ & f,g\in\mathcal{J}\Rightarrow f*g\in\mathcal{J} \end{align*} \]

其中 \(\mathcal{J}\) 为积性函数集（只是因为 \(\LaTeX\) 打中文太丑）

逆

对于数论函数 \(f\)，求其逆函数 \(g\)
考虑从 \(1\) 开始由小及大定义 \(g(n)\)，若 \(n > 1\) 已知 \(g(i),i\in[1,n)\)

\[\begin{align*} & (f*g)(n) = \sum_{d|n}g(d)f(\frac{n}{d})=0\\ \Leftrightarrow & \sum_{d\ne n\ d|n}g(d)f(\frac{n}{d})=-f(1)g(n)\\ \Leftrightarrow & g(n)=-\frac{1}{f(1)}\sum_{d\ne n\ d|n}g(d)f(\frac{n}{d}) \end{align*} \]

综合 \(g(1)=\frac{1}{f(1)}\)，有

\[g(n)=\begin{cases} -\frac{1}{f(1)}\sum_{d\ne n\ d|n}g(d)f(\frac{n}{d}) & n\ne 1\\ \frac{1}{f(1)} & n=1 \end{cases} \]

容易验证这就是 \(f\) 的逆。

迪利克雷生成函数[DGF]（懒得打飘号了）

定义

\(\{f\}\) 的迪利克雷生成函数为

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

性质

积性函数的值由 \(p^k\) 处确定，迪利克雷生成函数可以写作

\[F(x)=\prod_{p\in\mathcal{P}}(1+\frac{f(p)}{p^x}+\frac{f(p^2)}{p^{2x}}+\cdots) \]

两个数论函数的迪利克雷卷积的生成函数为这两个数论函数各自生成函数的点积

常见数论函数

常函数 \(\textbf{1}=Id_0\)

\(\textbf{1}\) 是无限维前缀和的系数。

\[\begin{align*} \zeta(n)&=\sum_{i\ge 1} \frac{1}{i^x} =\prod_{p\in\mathcal{P}}\frac{1}{1-p^{-x}} \end{align*} \]

欧拉函数 \(\varphi\)

\(\varphi(n)\) 为小于等于 \(n\) 并与 \(n\) 互质的正整数的个数。

\[\begin{align*} \varphi(p^k)=p^k-p^{k-1}\\ \Phi(x)=\frac{\zeta(x-1)}{\zeta(x)} \end{align*} \]

莫比乌斯函数 \(\mu\)

\(\mu\) 是无限维差分的系数，\(\mathbf{1}\) 的逆。

\[\begin{align*} &\mu(p^k)=\begin{cases} -1 & k=1\\ 0 & otherwise \end{cases} \\ &M(x)=\frac{1}{\zeta(x)} \end{align*} \]

标签：begin,frac,函数,数论,align,笔记,int,end
From： https://www.cnblogs.com/watware-cym/p/17179483.html