问题求解

liu_cheng_ao 2018-04-08 9:42:57 2018-04-09 0:04:20

关于「2018 集训队互测 Day 3」蒜头的奖杯一题,枚举所有两两最小公倍数不超过 n 的三元组做法的时间复杂度问题。

换句话说,就是要求:

f(n)=\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n [\mathrm{lcm}(i,j)\le n][\mathrm{lcm}(j,k)\le n][\mathrm{lcm}(i,k)\le n]

n \rightarrow +\infty 时的渐进增长率。

一个显然的上界是 O(n\sqrt{n}\log^3 n) ,因为 [\mathrm{lcm}(i,j)\le n] 的组数是 \Theta(n\ln^2n) ,而无向简单图的三元环个数是 O(|E|^{1.5})

一个显然的下界是 \Omega(n\sqrt{n}) ,因为 i\le j\le k\le \sqrt{n} 的三元组都符合条件。

但通过分析较小情况( \le 10^6 )的数值,我们猜想这个上界非常不满 …… 实际的增长率可能在 \Theta(n\sqrt n) 左右。

参见AoPS 求助帖


UPD 1

一个更好的上界是 O(n\sqrt{n}\log^{2.25}n)

对于一个 n ,我们设 1\le B\le \sqrt{n} ,那么,满足 k\le \frac{n}{B} 的三元组个数是 O((\frac{n}{B})^3) 的。

对于 k> \frac{n}{B} 的我们有:

\begin{eqnarray} g(n) & = & \sum_{k=\lceil\frac{n}{B}\rceil}^n\sum_{j=1}^k\sum_{i=1}^j [\mathrm{lcm}(i,j)\le n][\mathrm{lcm}(j,k)\le n][\mathrm{lcm}(i,k)\le n] \\ & \le & \sum_{k=\lceil\frac{n}{B}\rceil}^n(\sum_{j=1}^k [\mathrm{lcm}(j,k)\le n])(\sum_{i=1}^k [\mathrm{lcm}(i,k)\le n]) \\ & \le & \sum_{k=\lceil\frac{n}{B}\rceil}^n(\sum_{j=1}^n [\mathrm{lcm}(j,k)\le n])^2 \\ & \le & \sum_{k=\lceil\frac{n}{B}\rceil}^n(\sum_{d|k} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} [dj\frac{k}{d}\le n])^2 \\ & \le & \sum_{k=\lceil\frac{n}{B}\rceil}^n(\sigma_0(k)\lfloor\frac{n}{k}\rfloor)^2 \\ & = & O(\sum_{k=\lceil\frac{n}{B}\rceil}^n(\sigma_0(k)\frac{n}{k})^2) \\ & = & O(\sum_{i=1}^B\sum_{k=\lfloor\frac{n}{i+1}\rfloor+1}^{\lfloor\frac{n}{i}\rfloor}(\sigma_0(k)i)^2) \\ & = & O(\sum_{i=1}^B\sum_{k=1}^{\lfloor\frac{n}{i}\rfloor}\sigma_0^2(k)i) \\ & = & O(\sum_{i=1}^Bi\frac{n}{i}\log^3\frac{n}{i}) \\ & = & O(nB\log^3n) \\ \end{eqnarray}

可以解得,当 B=\Theta(\frac{\sqrt{n}}{\log^{0.75}n}) 时两部分之和取得最小值 O(n\sqrt{n}\log^{2.25}n)