莫比乌斯反演 & 狄利克雷卷积()

大家好,我不会数学实锤了。

文章内容较杂,分章节叙述了的大部分有关内容。

为什么把这俩放一起?我不知道。

积性函数

积性函数:\(\forall a,b\),\(a\perp b\),如果一个函数 \(f\) 始终满足 \(f(ab) = f(a)f(b)\),则称 \(f(x)\) 为积性函数。

常见的积性函数:

\(d(x) = \sum\limits_{i\mid n} 1\)

\(\sigma(x) = \sum\limits_{i\mid n} i\)

\(\varphi(x) = \sum\limits_{i=1}^{x}[\gcd(x,i)=1]\)(欧拉函数)

设 \(x=\prod\limits_{i=1}^{k}p_i^{\alpha_i}\),\(p_i\) 为质数。

\(
\mu(x) =
\begin{cases}
1 & x = 1 \\
0 & max\{\alpha_i\} > 1 \\
(-1)^k & \forall \alpha_i = 1 \\
\end{cases}
\)
(莫比乌斯函数)

若 \(f,g\) 为积性函数,则

  • \(h(x)=f(x^p)\)
  • \(h(x)=f^p(x)\)
  • \(h(x)=f(x)g(x)\)
  • \(h(x)=\sum\limits_{d\mid x}f(d)g(x/d)\)

中 \(h(x)\) 同为积性函数。

在处理莫比乌斯反演时,有时会要求出数论函数的前缀和,杜教筛可以用来快速处理此类问题。

狄利克雷卷积

有一个更好听的英文名字 。

Dirichlet 卷积

数论函数:定义域为正整数,陪域为复数的函数。数论函数中比较重要的运算法则为狄利克雷卷积。

可以发现数论函数是无限项的。

一个数论函数等于 \(0\),当且仅当 \(\forall f(x) = 0\)。

对于两个数论函数 \(f,g\),它们狄利克雷卷积的结果 \(h\) 定义为:

\(h(x) = \sum\limits_{d\mid x}^{}f(d)g(\frac{x}{d}) = \sum\limits_{ab=x}^{}f(a)g(b)\)

可以简记为 \(h=f*g\)。

狄利克雷卷积和狄利克雷生成函数有较大联系,不过本文不做讨论。

狄利克雷满足以下性质(\(f,g,h\) 均为数论函数):

  • 交换律 \(f*g=g*f\)
  • 结合律 \((f*g)*h=f*(g*h)\)
  • 分配律 \((f+g)*h=f*h+g*h\)
  • 数乘结合律 \((xf) * g = x(f*g)\),\(x\in R\)

简要证明一下第四条性质:

证明:记 \(h = f * g\),右式 \(=xh\)
左式 $= \sum\limits_{ab=n} xf(a)g(b) = x \sum\limits_{ab=n} f(a)g(b) = xh = $ 右式

证明:记 \(h = f * g\),右式 \(=xh\)

左式 $= \sum\limits_{ab=n} xf(a)g(b) = x \sum\limits_{ab=n} f(a)g(b) = xh = $ 右式

主要是一开始自己脑抽了一下没有想出来

其余均可自证不难。

单位元:单位函数 \(\varepsilon\) 是狄利克雷卷积中的单位元,对于任意数论函数 \(f(x)\),\(f*\varepsilon = f\)。据此可以求出 \(\varepsilon = \{1,0,0,0,\ldots\}\)。

零函数:\(0*f=0\)。

逆元:对于任意一个满足 \(f(x) \not = 0\) 的数论函数,如果有另一个数论函数 \(g(x)\),满足 \(f*g=\varepsilon\),则称 \(g(x)\) 是 \(f(x)\) 的逆元。逆元是唯一的。

\(g(x)\) 的表达式为:

接下来是一个重要结论:两个积性函数的狄利克雷卷积也是积性函数。

设 \(f,g\) 是积性函数,\(h=f*g\)。

设 \(\gcd(a,b) = 1\),则:

\(h(a)=\sum\limits^{}_{d1\mid a}f(d1)g\big(\frac{a}{d1}\big)\)

\(h(b)=\sum\limits^{}_{d2\mid b}f(d2)g\big(\frac{b}{d2}\big)\)

令 \(d = d1d2\),

\(h(a)h(b) = \sum\limits^{}_{d\mid ab}f(d)g\big(\frac{ab}{d}\big) = h(ab)\)

证毕。

由此我们有一个推论:积性函数的逆元也是积性的,证明留给读者思考。

莫比乌斯反演

前面我们提到了莫比乌斯函数,它也是个积性函数。这个函数还有如下性质:

\(
\sum\limits_{d\mid n} \mu(d)=
\begin{cases}
1 & n = 1 \\
0 & n \not = 1
\end{cases}
\)

注意到,这和 \(\varepsilon(n)\) 是相等的,\(\mu * 1 = \varepsilon\)。

令 \(n = \prod\limits_{i=1}^{k}p_i^{c_i},n’=\prod\limits_{i=1}^{k}p_i\)

由于含有平方项的因子 \(d\),\(\mu(d)=0\),因此 \(\sum\limits_{d\mid n}^{}\mu(d)=\sum\limits_{d\mid n’}^{}\mu(d)\)

而 \(\sum\limits_{d\mid n’}^{}\mu(d)=\sum\limits_{i=0}^{k}(-1)^i\binom{k}{i}=(1+(-1))^k\)

因此当 \(k=0\) 即 \(n=1\) 时答案为 \(1\),否则为 \(0\)。

反演结论:\([\gcd(i,j)=1]=\sum\limits_{d\mid\gcd(i,j)}^{}\mu(d)\)

如果 \(\gcd(i,j)=1\),\(\mu(1) = 1\)。

如果 \(\gcd(i,j)\not=1\),\(\sum\limits_{d\mid \gcd(i,j)}^{}\mu(d) = 0\)。

这个式子非常重要,强烈建议熟练背诵。

在上文,我们推导出了 \(\mu\) 函数是积性函数,因此可以线性求。

莫比乌斯变换中有两个常见变换形式可以用来反演,这里浅作记录:

  • 若 \(f(n)=\sum\limits_{d\mid n}^{}g(d)\),则 \(g(n) = \sum\limits_{d\mid n}^{}\mu(d)f\big(\frac{n}{d}\big)\)
    \(f(n)\) 称为 \(g(n)\) 的莫比乌斯变换,\(g(n)\) 称为 \(f(n)\) 的莫比乌斯逆变换,也就是莫比乌斯反演。
    我们进行拆分,发现 \(f(n)\) 相当于是 \(g(n)\) 与常数函数 \(1\) 的狄利克雷卷积。
    现在尝试证明上面的式子

    证明:我们希望能把 \(\sum\mu(d)\) 的贡献单独拆出来,尝试代入 \(f(n)\)
    \[\sum_{d\mid n} \mu(d) f\big(\frac{n}{d}\big)=\sum_{d\mid n}\mu(d)\sum_{k\mid(n/d)}g(k)
    \]尝试按照 \(g(k)\) 的贡献求和,上式可以变成
    \[\sum_{k\mid n}g(k) \sum_{d\mid (n/k)} \mu(d)
    \]当 \(\frac{n}{k}=1\) 时,\(g(k)\) 才有贡献,因此只有 \(n=k\) 时,原式存在贡献,故原式等价于 \(\sum\limits_{k\mid n}^{}[k=n]\cdot g(k)=g(n)\)
    证毕。

  • 若 \(f(n)=\sum\limits_{n\mid d}^{}g(d)\),则 \(g(n)=\sum\limits_{n\mid d}\mu\big(\frac{d}{n}\big)f(d)\)

    证明:逆推等号右边
    \[\begin{align*}
    & \sum_{n\mid d}^{}\mu\big(\frac d n\big)f(d) \\
    = & \sum_{k=1}^{}\mu(k)f(kn)\\
    = & \sum_{k=1}^{}\mu(k)\sum_{kn\mid d}g(d) \\
    = & \sum_{n\mid d}^{}g(d)\sum_{k\mid(d/n)}^{}\mu(k) \\
    = & \sum_{n\mid d}^{}g(d)\varepsilon\big(\frac{d}{n}\big)
    \end{align*}
    \]第三行推导第四行的原因是,我们从求 \(kn\) 能贡献的 \(d\),变成了对于一个 \(d\),有多少 \(k\) 能贡献。
    上文的反演结论,其实对应着 \(\varepsilon(n) = \sum\limits_{d\mid n}^{}\mu(d)\),故第四行可以推出第五行。
    综上,当 \(d=n\) 时,右式才会有贡献,因此等于 \(g(n)\),证毕。

做一做

1. [HAOI2011]Problem b

多测,\(a,b,c,d,k\) 给定。

首先经典容斥,记 \(f(i,j) = [gcd(i,j)=k]\)

将 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k]\) 转化一下

由反演结论

发现我们的时间复杂度并没有降低,考虑变化求和顺序,我们枚举 \(d\),那么 \(i,j\) 都是 \(d\) 的倍数,发现可以将原式化为

由下取整的性质可知,\(1\sim\lfloor \frac{n}{k}\rfloor\) 中 \(d\) 的倍数有 \(\lfloor \frac{n}{kd} \rfloor\) 个,故原式等于

可以用数论分块方式在根号时间解决。

预处理复杂度 \(\mathcal{O}(n)\)。

2. LCMSUM

多测 \(T \le 3 \times 10^5,n \le 10^6\)

根据小学奥数知识 \(\operatorname{lcm}(x,y)=\frac{xy}{\gcd(x,y)}\)

原式即

有一个数学中常用trick,将原式复制一份并倒序,提出 \(i=n\)

由辗转相除可得 \(\gcd(a,b)=gcd(b-a,b)\),分母可以合并,原式即

将 \(n\) 提回来

那么问题变成了根号或 \(\mathcal O(1)\) 求解 \(\sum\limits_{i=1}^{n}\frac{n^2}{\gcd(i,n)}\)

有一个想法是,设 \(d=\gcd(i,n)\),枚举 \(d\),此时 \(\gcd\big(\frac{i}{d},\frac{n}{d}\big)=1\)

统计与小于一个数且和这个数互质的函数当然学过——欧拉函数。

所以 \(\gcd(i,n)=d\) 的数有 \(\varphi(d)\) 个。原式可以转换为

考虑想办法将式子套出积性函数的样子,设 \(d’=\frac{n}{d}\),原式即

设 \(g(x) = \sum\limits_{d\mid x}^{} d \cdot \varphi(d)\),\(f_1(x)=x\) 为积性函数,\(f_2(x) = \varphi(x)\) 为积性函数,那么 \(f_1(x)f_2(x)\) 是积性函数,\(\sum\limits_{d\mid x}^{}f_1(d)f_2(d)\) 可以看作是 \(h(x)=1\) 和 \(f_1f_2\) 的狄利克雷卷积。上文我们已经论证了两个积性函数的狄利克雷卷积仍然是积性函数,所以 \(g(x)\) 是积性函数。

积性函数可以在线性时间内完成推导,这里给出推导过程:

设 \(\mathcal P\) 是素数集

\(g(p_i^k)\) 的值很容易表示,因为约数集确定在 \(p_i^0,p_i^1,\ldots,p_i^k\)。

\(g(p_i^k)=\sum\limits_{w=0}^{k}p_i^w\cdot\varphi(p_i^w)\)

\(\varphi(p_i^w)=p_i^{w-1}\cdot(p_i-1)\) 可以想象成将 \(p_i^w\) 分成 \(p_i^{w-1}\) 个段,每个段的最后一个显然是 \(p_i\) 的倍数。

所以 \(g(p_i^k)=p_i^{2w-1}\cdot(p_i-1)\)。

根据这上述式子,我们尝试将 \(g(p_i^{k+1})\) 表示出来

考虑线性筛中的下一个步骤,枚举 \(i \cdot p_j\)

如果 \(i\) 和 \(p_j\) 互质,这是朴素的。

接下来考虑 \(p_j\mid i\) 的情况,令 \(i=k\cdot p_j^w(\gcd(k,p_j)=1)\),

同理

所以将 \((2)\) 式代入 \((1)\) 式

预处理时间复杂度 \(\mathcal O(n)\),每个询问 \(\mathcal{O}(1)\) 回答。

3. UOJ #62 怎样跑得更快

\(n,c,d\) 给定,\(p = 998244353\),多测给出 \(b_i\),求 \(x_i\)。

记 \(f(i,j) = \gcd(i,j)\operatorname{lcm}(i,j)\)

有一个很好的思考方向,我们将线性方程组写成矩阵形式:

暴力求解,时间复杂度 \(\mathcal{O}(n^3q)\)。

当然你发现可以直接将 \(F\) 的逆矩阵处理出来每组询问直接乘 \(B\) 即可。

时间复杂度 \(\mathcal O(n^3+qn^2)\)。

接下来考虑正解,以下等号均看作模 \(p\) 意义下。

朴素地拆开 \(\operatorname{lcm}\),原式转化为

改写式子

设 \(f(x)=\sum\limits_{d\mid x}^{}f'(d)\),由莫比乌斯反演可知

\(f'(x)=\sum\limits_{d\mid x}f(d)\mu\big(\frac{x}{d}\big)\)

我们求 \(f'(x)\),这是 \(\mathcal O(n\log n)\) 的。

在实现的时候,有一个更好的式子,\(f'(x) = f(x) – \sum\limits_{d\mid n \land d\not=n}^{} f'(x)\),这个式子容斥可得。

回到原式,可以将 \(\gcd\) 拆掉,整个式子变成

移项

发现后一个 \(\sum\) 中只与 \(d\) 有关,考虑记为 \(r_d\),设 \(z(i) = b_i / g(i)\),式子变成

\(z(i)\) 已知,根据莫比乌斯反演,\(f'(i)r_i = \sum\limits_{d\mid i}^{}\mu(d)z\big(\frac{i}{d}\big)\)

\(f'(x)\) 可求,自然 \(r_x\) 可求。

接下来是一些细节,考虑到有除法,但 \(g(i)\) 和 \(h(i)\) 都不是 \(p\) 的倍数。

如果是 \(f'(x)\) 没有逆元:

  • \(f'(x)r_x\not=0\) 此时无解
  • \(f'(x)r_x=0\) 此时有多组解,随意给 \(r_x\) 赋值即可。

后记

因为笔者不精通数学,所以部分叙述和证明来自 oi-wiki,在此感谢 oi-wiki 的贡献者们!

————————

大家好,我不会数学实锤了。

文章内容较杂,分章节叙述了的大部分有关内容。

为什么把这俩放一起?我不知道。

积性函数

积性函数:\(\forall a,b\),\(a\perp b\),如果一个函数 \(f\) 始终满足 \(f(ab) = f(a)f(b)\),则称 \(f(x)\) 为积性函数。

常见的积性函数:

\(d(x) = \sum\limits_{i\mid n} 1\)

\(\sigma(x) = \sum\limits_{i\mid n} i\)

\(\varphi(x) = \sum\limits_{i=1}^{x}[\gcd(x,i)=1]\)(欧拉函数)

设 \(x=\prod\limits_{i=1}^{k}p_i^{\alpha_i}\),\(p_i\) 为质数。

\(
\mu(x) =
\begin{cases}
1 & x = 1 \\
0 & max\{\alpha_i\} > 1 \\
(-1)^k & \forall \alpha_i = 1 \\
\end{cases}
\)
(莫比乌斯函数)

若 \(f,g\) 为积性函数,则

  • \(h(x)=f(x^p)\)
  • \(h(x)=f^p(x)\)
  • \(h(x)=f(x)g(x)\)
  • \(h(x)=\sum\limits_{d\mid x}f(d)g(x/d)\)

中 \(h(x)\) 同为积性函数。

在处理莫比乌斯反演时,有时会要求出数论函数的前缀和,杜教筛可以用来快速处理此类问题。

狄利克雷卷积

有一个更好听的英文名字 。

Dirichlet 卷积

数论函数:定义域为正整数,陪域为复数的函数。数论函数中比较重要的运算法则为狄利克雷卷积。

可以发现数论函数是无限项的。

一个数论函数等于 \(0\),当且仅当 \(\forall f(x) = 0\)。

对于两个数论函数 \(f,g\),它们狄利克雷卷积的结果 \(h\) 定义为:

\(h(x) = \sum\limits_{d\mid x}^{}f(d)g(\frac{x}{d}) = \sum\limits_{ab=x}^{}f(a)g(b)\)

可以简记为 \(h=f*g\)。

狄利克雷卷积和狄利克雷生成函数有较大联系,不过本文不做讨论。

狄利克雷满足以下性质(\(f,g,h\) 均为数论函数):

  • 交换律 \(f*g=g*f\)
  • 结合律 \((f*g)*h=f*(g*h)\)
  • 分配律 \((f+g)*h=f*h+g*h\)
  • 数乘结合律 \((xf) * g = x(f*g)\),\(x\in R\)

简要证明一下第四条性质:

证明:记 \(h = f * g\),右式 \(=xh\)
左式 $= \sum\limits_{ab=n} xf(a)g(b) = x \sum\limits_{ab=n} f(a)g(b) = xh = $ 右式

证明:记 \(h = f * g\),右式 \(=xh\)

左式 $= \sum\limits_{ab=n} xf(a)g(b) = x \sum\limits_{ab=n} f(a)g(b) = xh = $ 右式

主要是一开始自己脑抽了一下没有想出来

其余均可自证不难。

单位元:单位函数 \(\varepsilon\) 是狄利克雷卷积中的单位元,对于任意数论函数 \(f(x)\),\(f*\varepsilon = f\)。据此可以求出 \(\varepsilon = \{1,0,0,0,\ldots\}\)。

零函数:\(0*f=0\)。

逆元:对于任意一个满足 \(f(x) \not = 0\) 的数论函数,如果有另一个数论函数 \(g(x)\),满足 \(f*g=\varepsilon\),则称 \(g(x)\) 是 \(f(x)\) 的逆元。逆元是唯一的。

\(g(x)\) 的表达式为:

接下来是一个重要结论:两个积性函数的狄利克雷卷积也是积性函数。

设 \(f,g\) 是积性函数,\(h=f*g\)。

设 \(\gcd(a,b) = 1\),则:

\(h(a)=\sum\limits^{}_{d1\mid a}f(d1)g\big(\frac{a}{d1}\big)\)

\(h(b)=\sum\limits^{}_{d2\mid b}f(d2)g\big(\frac{b}{d2}\big)\)

令 \(d = d1d2\),

\(h(a)h(b) = \sum\limits^{}_{d\mid ab}f(d)g\big(\frac{ab}{d}\big) = h(ab)\)

证毕。

由此我们有一个推论:积性函数的逆元也是积性的,证明留给读者思考。

莫比乌斯反演

前面我们提到了莫比乌斯函数,它也是个积性函数。这个函数还有如下性质:

\(
\sum\limits_{d\mid n} \mu(d)=
\begin{cases}
1 & n = 1 \\
0 & n \not = 1
\end{cases}
\)

注意到,这和 \(\varepsilon(n)\) 是相等的,\(\mu * 1 = \varepsilon\)。

令 \(n = \prod\limits_{i=1}^{k}p_i^{c_i},n’=\prod\limits_{i=1}^{k}p_i\)

由于含有平方项的因子 \(d\),\(\mu(d)=0\),因此 \(\sum\limits_{d\mid n}^{}\mu(d)=\sum\limits_{d\mid n’}^{}\mu(d)\)

而 \(\sum\limits_{d\mid n’}^{}\mu(d)=\sum\limits_{i=0}^{k}(-1)^i\binom{k}{i}=(1+(-1))^k\)

因此当 \(k=0\) 即 \(n=1\) 时答案为 \(1\),否则为 \(0\)。

反演结论:\([\gcd(i,j)=1]=\sum\limits_{d\mid\gcd(i,j)}^{}\mu(d)\)

如果 \(\gcd(i,j)=1\),\(\mu(1) = 1\)。

如果 \(\gcd(i,j)\not=1\),\(\sum\limits_{d\mid \gcd(i,j)}^{}\mu(d) = 0\)。

这个式子非常重要,强烈建议熟练背诵。

在上文,我们推导出了 \(\mu\) 函数是积性函数,因此可以线性求。

莫比乌斯变换中有两个常见变换形式可以用来反演,这里浅作记录:

  • 若 \(f(n)=\sum\limits_{d\mid n}^{}g(d)\),则 \(g(n) = \sum\limits_{d\mid n}^{}\mu(d)f\big(\frac{n}{d}\big)\)
    \(f(n)\) 称为 \(g(n)\) 的莫比乌斯变换,\(g(n)\) 称为 \(f(n)\) 的莫比乌斯逆变换,也就是莫比乌斯反演。
    我们进行拆分,发现 \(f(n)\) 相当于是 \(g(n)\) 与常数函数 \(1\) 的狄利克雷卷积。
    现在尝试证明上面的式子

    证明:我们希望能把 \(\sum\mu(d)\) 的贡献单独拆出来,尝试代入 \(f(n)\)
    \[\sum_{d\mid n} \mu(d) f\big(\frac{n}{d}\big)=\sum_{d\mid n}\mu(d)\sum_{k\mid(n/d)}g(k)
    \]尝试按照 \(g(k)\) 的贡献求和,上式可以变成
    \[\sum_{k\mid n}g(k) \sum_{d\mid (n/k)} \mu(d)
    \]当 \(\frac{n}{k}=1\) 时,\(g(k)\) 才有贡献,因此只有 \(n=k\) 时,原式存在贡献,故原式等价于 \(\sum\limits_{k\mid n}^{}[k=n]\cdot g(k)=g(n)\)
    证毕。

  • 若 \(f(n)=\sum\limits_{n\mid d}^{}g(d)\),则 \(g(n)=\sum\limits_{n\mid d}\mu\big(\frac{d}{n}\big)f(d)\)

    证明:逆推等号右边
    \[\begin{align*}
    & \sum_{n\mid d}^{}\mu\big(\frac d n\big)f(d) \\
    = & \sum_{k=1}^{}\mu(k)f(kn)\\
    = & \sum_{k=1}^{}\mu(k)\sum_{kn\mid d}g(d) \\
    = & \sum_{n\mid d}^{}g(d)\sum_{k\mid(d/n)}^{}\mu(k) \\
    = & \sum_{n\mid d}^{}g(d)\varepsilon\big(\frac{d}{n}\big)
    \end{align*}
    \]第三行推导第四行的原因是,我们从求 \(kn\) 能贡献的 \(d\),变成了对于一个 \(d\),有多少 \(k\) 能贡献。
    上文的反演结论,其实对应着 \(\varepsilon(n) = \sum\limits_{d\mid n}^{}\mu(d)\),故第四行可以推出第五行。
    综上,当 \(d=n\) 时,右式才会有贡献,因此等于 \(g(n)\),证毕。

做一做

1. [HAOI2011]Problem b

多测,\(a,b,c,d,k\) 给定。

首先经典容斥,记 \(f(i,j) = [gcd(i,j)=k]\)

将 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k]\) 转化一下

由反演结论

发现我们的时间复杂度并没有降低,考虑变化求和顺序,我们枚举 \(d\),那么 \(i,j\) 都是 \(d\) 的倍数,发现可以将原式化为

由下取整的性质可知,\(1\sim\lfloor \frac{n}{k}\rfloor\) 中 \(d\) 的倍数有 \(\lfloor \frac{n}{kd} \rfloor\) 个,故原式等于

可以用数论分块方式在根号时间解决。

预处理复杂度 \(\mathcal{O}(n)\)。

2. LCMSUM

多测 \(T \le 3 \times 10^5,n \le 10^6\)

根据小学奥数知识 \(\operatorname{lcm}(x,y)=\frac{xy}{\gcd(x,y)}\)

原式即

有一个数学中常用trick,将原式复制一份并倒序,提出 \(i=n\)

由辗转相除可得 \(\gcd(a,b)=gcd(b-a,b)\),分母可以合并,原式即

将 \(n\) 提回来

那么问题变成了根号或 \(\mathcal O(1)\) 求解 \(\sum\limits_{i=1}^{n}\frac{n^2}{\gcd(i,n)}\)

有一个想法是,设 \(d=\gcd(i,n)\),枚举 \(d\),此时 \(\gcd\big(\frac{i}{d},\frac{n}{d}\big)=1\)

统计与小于一个数且和这个数互质的函数当然学过——欧拉函数。

所以 \(\gcd(i,n)=d\) 的数有 \(\varphi(d)\) 个。原式可以转换为

考虑想办法将式子套出积性函数的样子,设 \(d’=\frac{n}{d}\),原式即

设 \(g(x) = \sum\limits_{d\mid x}^{} d \cdot \varphi(d)\),\(f_1(x)=x\) 为积性函数,\(f_2(x) = \varphi(x)\) 为积性函数,那么 \(f_1(x)f_2(x)\) 是积性函数,\(\sum\limits_{d\mid x}^{}f_1(d)f_2(d)\) 可以看作是 \(h(x)=1\) 和 \(f_1f_2\) 的狄利克雷卷积。上文我们已经论证了两个积性函数的狄利克雷卷积仍然是积性函数,所以 \(g(x)\) 是积性函数。

积性函数可以在线性时间内完成推导,这里给出推导过程:

设 \(\mathcal P\) 是素数集

\(g(p_i^k)\) 的值很容易表示,因为约数集确定在 \(p_i^0,p_i^1,\ldots,p_i^k\)。

\(g(p_i^k)=\sum\limits_{w=0}^{k}p_i^w\cdot\varphi(p_i^w)\)

\(\varphi(p_i^w)=p_i^{w-1}\cdot(p_i-1)\) 可以想象成将 \(p_i^w\) 分成 \(p_i^{w-1}\) 个段,每个段的最后一个显然是 \(p_i\) 的倍数。

所以 \(g(p_i^k)=p_i^{2w-1}\cdot(p_i-1)\)。

根据这上述式子,我们尝试将 \(g(p_i^{k+1})\) 表示出来

考虑线性筛中的下一个步骤,枚举 \(i \cdot p_j\)

如果 \(i\) 和 \(p_j\) 互质,这是朴素的。

接下来考虑 \(p_j\mid i\) 的情况,令 \(i=k\cdot p_j^w(\gcd(k,p_j)=1)\),

同理

所以将 \((2)\) 式代入 \((1)\) 式

预处理时间复杂度 \(\mathcal O(n)\),每个询问 \(\mathcal{O}(1)\) 回答。

3. UOJ #62 怎样跑得更快

\(n,c,d\) 给定,\(p = 998244353\),多测给出 \(b_i\),求 \(x_i\)。

记 \(f(i,j) = \gcd(i,j)\operatorname{lcm}(i,j)\)

有一个很好的思考方向,我们将线性方程组写成矩阵形式:

暴力求解,时间复杂度 \(\mathcal{O}(n^3q)\)。

当然你发现可以直接将 \(F\) 的逆矩阵处理出来每组询问直接乘 \(B\) 即可。

时间复杂度 \(\mathcal O(n^3+qn^2)\)。

接下来考虑正解,以下等号均看作模 \(p\) 意义下。

朴素地拆开 \(\operatorname{lcm}\),原式转化为

改写式子

设 \(f(x)=\sum\limits_{d\mid x}^{}f'(d)\),由莫比乌斯反演可知

\(f'(x)=\sum\limits_{d\mid x}f(d)\mu\big(\frac{x}{d}\big)\)

我们求 \(f'(x)\),这是 \(\mathcal O(n\log n)\) 的。

在实现的时候,有一个更好的式子,\(f'(x) = f(x) – \sum\limits_{d\mid n \land d\not=n}^{} f'(x)\),这个式子容斥可得。

回到原式,可以将 \(\gcd\) 拆掉,整个式子变成

移项

发现后一个 \(\sum\) 中只与 \(d\) 有关,考虑记为 \(r_d\),设 \(z(i) = b_i / g(i)\),式子变成

\(z(i)\) 已知,根据莫比乌斯反演,\(f'(i)r_i = \sum\limits_{d\mid i}^{}\mu(d)z\big(\frac{i}{d}\big)\)

\(f'(x)\) 可求,自然 \(r_x\) 可求。

接下来是一些细节,考虑到有除法,但 \(g(i)\) 和 \(h(i)\) 都不是 \(p\) 的倍数。

如果是 \(f'(x)\) 没有逆元:

  • \(f'(x)r_x\not=0\) 此时无解
  • \(f'(x)r_x=0\) 此时有多组解,随意给 \(r_x\) 赋值即可。

后记

因为笔者不精通数学,所以部分叙述和证明来自 oi-wiki,在此感谢 oi-wiki 的贡献者们!