和式简单推倒技巧

白简のBlog / 2023-08-21 / 原文

整除枚举变换为区间枚举

\[\sum_{d \mid n}d=\sum^{n}_{i=1} \left[i \mid n \right] \cdot i \]

我们枚举的东西叫做指标，例如上面的 \(d\) 和 \(i\)。

指标变换（重要！！！）

给定一个整数 \(d\)，对于下面这种和式，我们就可以变换指标。

\[\sum_{i = 1}^n\sum_{j = 1}^n \left[ \gcd(i,j) = d\right] \]

我们令 \(i=i' \cdot d,j=j' \cdot d\)。

由于后面艾弗森括号中要求 \(i,j\) 都包含因子 \(d\)，如果枚举的 \(i,j\) 不都是 \(d\) 的倍数时不会产生贡献。

所以我们可以不一个一个地枚举 \(i,j\)，而是直接枚举 \(d\) 的倍数，有：

\[\sum_{i'd = 1}^n\sum_{j'd = 1}^n \left[ \gcd(i'd,j'd) = d\right] \]

然后可以变换枚举范围，这里 \(i\) 的起点本来应该是 \(\left\lfloor\\\frac{1}{d}\right\rfloor\)，但是 \(0\) 的情况没有必要讨论，所以我们从 \(1\) 开始。

因为我们后面的艾弗森括号只有 \(1\) 和 \(0\) 两种取值，也就是说我们统计的只是公约数为 \(d\) 的数对个数，所以可以进行以下的变换。

\[\sum_{i = 1}^{\left\lfloor\\\frac{n}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\\\frac{n}{d}\right\rfloor} \left[ \gcd(i,j) = 1\right]\]

那么现在我们发现后面艾弗森括号里面的东西可以通过 \(\mu * I=\varepsilon\) 进行莫比乌斯函数。

下面的部分和莫比乌斯反演有关。

交换求和次序

刚才那个式子可以利用莫比乌斯函数性质转化成下面这样

\[\sum_{i = 1}^{\left\lfloor\\\frac{n}{d}\right\rfloor}\sum_{j = 1}^{\left\lfloor\\\frac{n}{d}\right\rfloor}\sum_{k |(i,j)} \mu(k) \]

这个 \(d \mid \gcd(i,j)\) 等价于 \(\left[ d \mid i \right] \land \left[ d \mid j \right]\)，即 \(d\) 同时是 \(i\) 和 \(j\) 的因子。

那么我们可以把式子转化为：

\[\sum_{i = 1}^n\sum_{j = 1}^n\sum_{k =1}^n \left[d\mid i\right] \left[d \mid j \right] \ \mu(k) \]

\(k\) 的取值与 \(i,j\) 无关，我们可以把 \(\mu(k)\) 提到前面去。

\[\sum_{k =1}^n \mu(k) \sum_{i = 1}^n \left[d\mid i\right] \sum_{j = 1}^n \left[d \mid j \right] \]

转换为整除分块形式

对于上面的式子，我们可以把后面两部分进行整除分块。

\[\sum_{i=1}^n \left[ d \mid i \right]=\left\lfloor \dfrac{n}{d} \right\rfloor \]

这个式子表示的是，当 \(d\) 确定时，区间 \(\left[ 1,n \right]\) 中有多少个整数是 \(d\) 的倍数，即 \(\left\lfloor\dfrac{n}{d} \right\rfloor\) 个。

\[\text{END} \]