SDOI2015 约数和

这里准备D死Cage.

题外话，这个题是我2019首次AC的，现在都2021年末了，我竟然又沦落到看题解的地步了。

---

link

问： \[ \sum_{i}^n\sum_{j}^m d(i\cdot j) \] 问题逃不开的就是如何解决 \(d(i\cdot j)\)。

Wrong Solution 1

我首先是错误的考虑了 \(d\) 的积性，并没有意识到 \((i,j)\not =1\) 时这个东西是多么难处理，这个导致我浪费了30mins。

但是，我认识到了 \(d\) 的积性是如此的难处理，或者说成他的积性是如此的弱。

---

Wrong Solution 2

接下来我开始考虑能否用约数性质，很显然如果枚举约数 \(t\) 那么枚举量就会飙升到 \(nm\) 级别，仍然很难处理。

---

尽管我也想到这个积性可不可以拆开做文章，但是讲道理因为第一次错误认识积性，我现在有 \(d\) 积性 ptsd。所以没想。

所以我挂了，写下了这篇总结性质的题解。

---

More Acceptable Solution 2

首先我们还是得从拆 \((i\cdot j)\) 考虑。

我们先硬着头皮把他当成完全积性，看会发生什么。

Compare \(d(i\cdot j)\) with \(d(i)\cdot d(j)\)。

一个很自然的感觉是我应该会算重，但是在考虑算重之前，我们想一想为什么会不算漏。

我们现在是枚举 \(i,j\) 的因子，然后在乘起来，我们考虑对 \(i\cdot j\) 进行质因数分解。\(i\cdot j =\prod p_i^{a_i}\)

对于 \(i\cdot j\) 的一个因子 \(t\) ，有 \(t=\prod p_i^{b_i},b_i<a_i\)，考虑 \(a_i\) 肯定是被分给了 \(i\),\(j\)了。

所以很简单的逻辑，我们优先从 \(a\) 中选因子 \(p_i\) ，如果选光了还达不到，就在 \(b_i\) 选。

所以一定不会算漏，接下来考虑如何不算重。

---

考虑现在本质上是在钦定一个因子如何划分，为了不算重我们就应钦定一些东西。

这里比较自然的，我们想到，我要像证明”不会算漏“那样，尽可能在第一个数中选。

所以如果第一个数还能选 \(p_i\)，此时 却在第二个数中选，这就被认为不合法。

形式化的如果第一个数是 \(i\) 选因子 \(a\),第二个数 \(j\) 选因子 \(b\)，那么需要满足 \((\frac{i}{a},b)=1\)。

---

如此，我们成功的拆开了 \(d(i\cdot j)\) 。

得到了那个家喻户晓臭名昭著 的式子： \[ d(i\cdot j)=\sum_{a|i}\sum_{b|j}[(\frac{i}{a},b)=1]=\sum_{a|i}\sum_{b|j}[(a,b)=1] \] 这个题接下来就变成傻逼题了。 \[ \begin{aligned} \sum_{i,j}\sum_{a|i}\sum_{b|j}\gcd(a,b)=1\\ \sum_{a,b}\sum_{a|i}\sum_{b|j}\gcd(a,b)=1\\ \sum_{a,b}[\gcd(a,b)=1]\lfloor\frac{n}{a}\rfloor\lfloor\frac{m}{b}\rfloor\\ \sum_d\mu(d)\sum_{d|a,d|b}\lfloor\frac{n}{a}\rfloor\lfloor\frac{m}{b}\rfloor\\ \end{aligned} \] 如何快速求： \[ \sum_{a=1}^{n/d}\lfloor\frac{n}{da}\rfloor \]

\[ \sum_{a=1}^{n/d}\lfloor\frac{n}{da}\rfloor=\sum_{a=1}^{n/d}\lfloor\frac{\frac{n}{d}}{a}\rfloor \]

合理发现这个东西是个关于 \(n/d\) 的函数，直接 sqrt预处理即可。

done.