【循环之美】的多种解法详解

· · 题解

这是一道一题多解的题。

为了防止算重，我们可以只计算最简分数的贡献。根据小奥学习的知识，如果 x/y 是最简分数当且仅当 x\perp y。（这里的 \perp 是互质的意思）

然后考虑到是 k 进制下纯循环小数，所以一定有 y\perp k。

于是题目就变成了求

\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]

下面给出一大波解法：

法一：

\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k] =\sum_{d=1}^n\mu(d)\sum_{i=1}^\frac{n}{d}\sum_{j=1}^\frac{m}{d}[jd\perp k]

为了方便，这里的分数默认向下取整。

=\sum_{d=1}^n\mu(d)\frac{n}{d}[d\perp k]\sum_{j=1}^\frac{m}{d}[j\perp k]

设 g(x)=\sum_{i=1}^x[i\perp k]，那么显然，g(x)=g(x\mod k)+\frac{x}{k}\varphi(k)

这一坨可以快速算出，那么原式

=\sum_{d=1}^n\mu(d)\frac{n}{d}[d\perp k]g(\frac{m}{d})

再设f(n,k)=\sum_{i=1}^n\mu(i)[i\perp k]，那么原式

=\sum_{l,r}(f(r,k)-f(l-1,k))\frac{n}{d}g(\frac{m}{d})

其中 l,r 是数论分块的每个区间。

现在考虑如何计算f

f(n,k)=\sum_{i=1}^n\mu(i)[i\perp k] =\sum_{d|k}\mu(d)\sum_{i=1}^\frac{n}{d}\mu(id)

由 \mu(ab)=\mu(a)\mu(b)[a\perp b] 得：

=\sum_{d|k}\mu^2(d)\sum_{i=1}^\frac{n}{d}\mu(i)[i\perp d] =\sum_{d|k}\mu^2(d)f(\frac{n}{d},d)

边界用杜教筛算一算即可。

法二：

考虑法一的 f(n,k) 有没有什么更好的计算方法。

设 p 是 k 的一个质因子，我们可以发现，我们其实并不关注 k 中每一个质因子出现的个数，我们只关注其是否出现，那么我们先把 k 中的每个超过一次的质因子变成一次，然后根据容斥可得：

f(n,k)=\sum_{i=1}^n\mu(i)[i\perp k/p]-\sum_{i=1}^n\mu(i)[i\perp k/p][p|i] =f(n,k/p)-\sum_{i=1}^\frac{n}{p}\mu(ip)[ip\perp k/p]

显然 \mu(p)=-1，还是按照刚才的套路：

=f(n,k/p)+\sum_{i=1}^\frac{n}{p}\mu(i)[i\perp k/p][i\perp p] =f(n,k/p)+f(\frac{n}{p},k)

法三：

我们发现法一和法二都需要多次计算 f，能不能减少一点呢？

当然能，首先回到法一的某一步，得到原式

=\sum_{d=1}^n\mu(d)\frac{n}{d}[d\perp k]g(\frac{m}{d})

盯着这货看，发现好像有什么东西……

我们设 \displaystyle F(x,k)=\sum_{d=1}^\frac{n}{x}\mu(d)\frac{n}{xd}[d\perp k]g(\frac{m}{xd}) 那么答案就是 F(1,k)

F(x,k)=\sum_{d=1}^\frac{n}{x}\mu(d)\frac{n}{xd}\sum_{a|d,a|x}\mu(a)g(\frac{m}{xd}) =\sum_{a|x}\mu(a)\sum_{d=1}^\frac{n}{ax}\frac{n}{axd}\mu(ad)g(\frac{m}{axd}) =\sum_{a|x}\mu^2(a)\sum_{d=1}^\frac{n}{ax}\frac{n}{axd}\mu(d)[a\perp d]g(\frac{m}{axd}) =\sum_{a=1}^x\mu^2(a)F(ax,a)

边界为 a=1 或者 x>\min(n,m)，杜教筛随便搞搞就可以了。

法四：

来自一位大佬的神仙做法 还是考虑计算 f(n,k) ，不过这次我们设的是一元函数，即 f(n)=\sum_{i=1}^n\mu(i)[i\perp k]，开始搞事情。

f(n)=\sum_{i=1}^n[i\perp k]f(\frac{n}{i})-\sum_{i=2}^n[i\perp k]f(\frac{n}{i})

考虑如何计算 \sum_{i=1}^n[i\perp k]f(\frac{n}{i})

=\sum_{i=1}^nf(\frac{n}{i})=\sum_{i=1}^n[i\perp k]\sum_{j=1}^\frac{n}{i}[j\perp k]\mu(j) =\sum_{i=1}^nf(\frac{n}{i})=\sum_{i=1}^n\sum_{j=1}^\frac{n}{i}[ij\perp k]\mu(j) \sum_{T=1}^n[T\perp k]\sum_{d|T}\mu(d)

显然，后面那一坨只有在 T=1 时值为 1，其他时候值为 0，于是就变成了

f(n)=1-\sum_{i=2}^n[i\perp k]f(\frac{n}{i})

注意到后面那一坨跟 g 有关，可以快速算出，于是杜教筛即可。

法五：

刚才我们一直在 [i\perp j] 上下功夫，我们能不能在 [j\perp k] 上下功夫呢？当然可以，于是原式

=\sum_{i=1}^n\sum_{j=1}^m[i\perp j]\sum_{d|k,d|j}\mu(d) =\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^\frac{m}{d}[i\perp jd] =\sum_{d|k}\mu(d)\sum_{i=1}^n\sum_{j=1}^\frac{m}{d}[i\perp j][i\perp d]

咦，好像……

我们设 \displaystyle S(n,m,k)=\sum_{i=1}^n\sum_{j=1}^m[i\perp j][j\perp k]

那么就有

S(n,m,k)=\sum_{d|k}\mu(d)S(\frac{m}{d},n,d)

递归计算即可。

法六：

刚才我们一直都只反演了一个，能不能同时反演两个呢？显然是可以的。

式子比较板，且和第一种相似，过程较长，留给读者自行思考。

（如果你还有什么新方法可以来告诉本蒟蒻哦）

update 2021.7.15 纠正了 tommy0103 提出的一个错误

update 4.6 修改了一处小错误（话说竟然没有人发现）