下文我们使用 lowZ\text{lowZ}lowZ 来表示美丽度，即二进制表示后末尾连续 000 的个数。
首先这里存在一个不易观察到的结论：
在题目的要求下，f(a,b,c)f(a,b,c)f(a,b,c) 的答案，即 lowZ(∣ac−bc∣)\text{lowZ}(|a^c-b^c|)lowZ(∣ac−bc∣)，实际上只与 lowZ(∣a−b∣)\text{lowZ}(|a-b|)lowZ(∣a−b∣) 相关。关于这部分在末尾会给出初等证明。
因此题目要求的东西，实际上和 ccc 是无关的，我们只需要求若干个 lowZ(∣a−b∣)\text{lowZ}(|a-b|)lowZ(∣a−b∣) 就可以了。
题目中所说的前 nnn 个正奇数，对应的就是 1,3,5,⋯ ,2n−11,3,5,\cdots,2n-11,3,5,⋯,2n−1。任意奇数都可以表示成 2x−12x-12x−1 的形式，我们取两个奇数 aaa 和 bbb，分别表示为 a=2i−1a = 2i-1a=2i−1 和 b=2j−1b=2j-1b=2j−1。
显然 ∣a−b∣=2∣i−j∣|a-b| = 2|i-j|∣a−b∣=2∣i−j∣，我们尝试表示 lowZ(∣a−b∣)\text{lowZ}(|a-b|)lowZ(∣a−b∣)：
lowZ(∣a−b∣)=lowZ(2∣i−j∣)=lowZ(∣i−j∣)+1\begin{equation*} \text{lowZ}(|a-b|) = \text{lowZ}(2|i-j|) = \text{lowZ}(|i-j|) + 1 \end{equation*} lowZ(∣a−b∣)=lowZ(2∣i−j∣)=lowZ(∣i−j∣)+1
第二步转化是显然的，一个数字乘以二等价于左移一位，所以末尾会多一个 000。
那么我们记最后的答案为 ansansans，则有：
ans=∑a≠blowZ(∣a−b∣)=∑a≠b(lowZ(∣i−j∣)+1)\begin{equation*} ans = \sum_{a\neq b} \text{lowZ}(|a-b|) = \sum_{a\neq b} (\text{lowZ}(|i-j|) + 1) \end{equation*} ans=a=b∑ lowZ(∣a−b∣)=a=b∑ (lowZ(∣i−j∣)+1)
我们可以发现 a≠ba\neq ba=b 这个东西实际上是具有对称性的，因此上面这个式子可以进一步化简成：
n(n−1)+2∑i>jlowZ(i−j)\begin{equation*} n(n-1) + 2 \sum_{i>j} \text{lowZ} (i-j) \end{equation*} n(n−1)+2i>j∑ lowZ(i−j)
n(n−1)n(n-1)n(n−1) 是好算的，后面这一部分看起来并不好算，我们只要想出来怎么计算后面这一式子就可以了。
我们思考一下，对于若干个满足条件的 (i,j)(i,j)(i,j) 实际上我们在求贡献的时候，可以把其看做 t∗2kt * 2^kt∗2k，其中 ttt 是一个奇数。我们不妨尝试计算对于每一个 kkk 有多少满足条件的 ttt。
这里要记住，我们的 iii 和 jjj 表达的实际上是我们对于前 nnn 个正整数编号之后，iii 和 jjj 就表示了他们是这个正奇数数列中的第几项。
接下来这部分很重要：
我们枚举所有的 2k2^k2k，定义 mmm 为其最大序号差值，即 n−1n-1n−1。
这样一来我们可以使用 mmm 除以 2k2^k2k，来表示 t∗2kt * 2^kt∗2k 中，我们最大可以取到的 ttt。
因为我们上面说了 ttt 一定是一个奇数，我们定义 q=m/2kq = m / 2^kq=m/2k所以这里我们可以使用 q−(q/2)q - (q / 2)q−(q/2) 来计算出 ttt 能取到多少个奇数，我们记其为 cntkcnt_kcntk ，这个计算是平凡的，这里就不证明了。
之后我们记 s=(q+1)/2s = (q + 1) / 2s=(q+1)/2，这个的平方就是前 sss 个奇数的和，这个的证明也是平凡的，可以使用等差数列的求和公式。
于是我们可以用 2k2^k2k 乘以 s2s^2s2 来计算出所有 t∗2kt * 2^kt∗2k 的和。
对于每一个 ttt，它对应的 d=t∗2kd = t * 2^kd=t∗2k 在 1≤t∗2k≤m1\leq t * 2^k \leq m1≤t∗2k≤m 这个区间里出现的次数有 m+1−dm+1-dm+1−d 次，其证明就是我们通过固定 ddd，则 iii 一定在 [1,m−d+1][1,m-d+1][1,m−d+1] 的区间里。
于是我们可以合理地计算出贡献了：
贡献=k∗∑t(m+1−d)=k∗∑t(m+1−t∗2k)\begin{equation*} 贡献 = k * \sum_t (m+1-d) = k * \sum_t (m+1-t*2^k) \end{equation*} 贡献=k∗t∑ (m+1−d)=k∗t∑ (m+1−t∗2k)
我们对最右边的式子进行拆分求和，就变成：
k∗((m+1)×cntk−2k×∑tt)\begin{equation*} k * ((m+1)\times cnt_k - 2^k \times \sum_t t) \end{equation*} k∗((m+1)×cntk −2k×t∑ t)
推到这个式子，已经就结束了，我们可以在 O(logn)O(\log n)O(logn) 的复杂度内求解单组解。
最后计算答案的时候，总三元组个数有 n(n−1)(n−2)n(n-1)(n-2)n(n−1)(n−2) 个，所以我们有：
n(n−1)+2×sumn(n−1)(n−2)=1+2×sumn(n−1)\begin{equation*} \frac{n(n-1)+2\times sum}{n(n-1)(n-2)} = 1 + \frac{2\times sum}{n(n-1)} \end{equation*} n(n−1)(n−2)n(n−1)+2×sum =1+n(n−1)2×sum
最后给出文章一开始提到的结论的初等证明：
首先 aaa 与 bbb 是奇数，因此 a−ba-ba−b 一定是一个偶数，我们将其表示为 t∗2kt * 2^kt∗2k。
我们对 ac−bca^c-b^cac−bc 做一个分解：
ac−bc=(a−b)×(ac−1+ac−2b+⋯+bc−1)。\begin{equation*} a^c - b^c = (a-b)\times (a^{c-1}+a^{c-2}b+\cdots +b^{c-1})。 \end{equation*} ac−bc=(a−b)×(ac−1+ac−2b+⋯+bc−1)。
我们记其第二个因子为 CCC，因为 aaa 与 bbb 均为奇数，奇数的次幂一定是奇数，因此 CCC 中的每一项都是奇数，共有奇数项，因此 CCC 一定是一个奇数。
于是我们就可以进行如下的拆解：
∣ac−bc∣=∣a−b∣∗C=t∗2k∗C\begin{equation*} |a^c - b^c| = |a-b| * C = t * 2^k * C \end{equation*} ∣ac−bc∣=∣a−b∣∗C=t∗2k∗C
因为 ttt 与 CCC 为奇数是肯定的，因此 lowZ\text{lowZ}lowZ 与且仅与 2k2^k2k 相关，也就是与 CCC 无关，只和 ∣a−b∣|a-b|∣a−b∣ 相关。
文章开头的结论得证。
虽然这个题的 ttt 与 nnn 等阶，我这种做法和 O(nlogn)O(n\log n)O(nlogn) 预处理之后 O(1)O(1)O(1) 求解单组的时间复杂度一样，但是单组 O(logn)O(\log n)O(logn) 可以求解更大的 nnn。
