版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: 随笔 - 从卷积的结合律看多重求和 categories:
$\;$
<!-- more -->在证明卷积的结合律时, 会涉及到二重求和的处理
$$ \begin{aligned} f(gh)(n)&=\sum{e|n}f(e)\sum{d'|\frac{n}{e}}g(d')h\left(\frac{n}{d'e}\right)\ &=\sum{e|n}\sum{d'|\frac{n}{e}}f(e)g\left(d'\right)h\left(\frac{n}{d'e}\right)\ &=\sum{d|n}\sum{e|d}f(e)g\left(\frac{d}{e}\right)h\left(\frac{n}{d}\right)\ &=\sum_{abc=n}f(a)g(b)h(c) \end{aligned} $$
其中第二个等号与第三个等号的转化值得注意, 它分为如下过程:
$$ \sum{e\mid n}\sum{d'\mid\frac{n}{e}}\xrightarrow[(1)]{d'\to\frac{d}{e}}\sum{e\mid n}\sum{\frac{d}{e}\mid\frac{n}{e}}\xrightarrow[(2)]{}\sum{e\mid n}\sum{e\mid d\mid n}\xrightarrow[(3)]{\text{Swap}}\sum{d\mid n}\sum{e\mid d} $$
其中:
$(1)$ 就是换元
$(2)$ 依赖如下定理:
{% note success no-icon %}
<a id="th-1-1">定理 - 1-1</a>
$$ \frac{d}{e}\mid \frac{n}{e}\iff e\mid d\mid n $$
<details open> <summary>证明</summary> - $\implies$ 一方面 $$ \frac{d}{e}\mid \frac{n}{e}\implies \left(e\cdot\frac{d}{e}\right)\mid \left(e\cdot\frac{n}{e}\right)\implies d\mid n $$ 另一方面 $$ \frac{d}{e}\in\mathbb{Z}\implies e\mid d $$ 故 $e\mid d\mid n$ - $\impliedby$ 由 $e\mid d\mid n$ 可知 $$ \frac{n}{e},\frac{n}{d},\frac{d}{e}\in\mathbb{Z} $$ 又 $$ \frac{n}{e}=\frac{n}{d}\cdot\frac{d}{e} $$ 故 $$ \frac{d}{e}\mid \frac{n}{e} $$ </details>{% endnote %}
$(3)$ 即是交换枚举顺序, 即 先枚举 $e$ 后枚举 $d\longrightarrow$ 先枚举 $d$ 后枚举 $e$
交换前即为先枚举 $n$ 的因子 $e$, 再枚举 $d$ 满足既是 $n$ 的因子也是 $e$ 的倍数
交换后即为先枚举 $n$ 的因子 $d$, 再枚举 $e$ 满足既是 $n$ 的因子也是 $d$ 的因子, 即枚举 $d$ 的因子 $e$