2017 Multi-University Training Contest 8 总结

这场队友带飞,自己只写了一题数论题,正好是最近学习的那一个类型,虽然做的复杂了,不过好歹也做出来了。
 

1002 Battlestation Operational

F(n) = \sum_{i=1}^{n} \lceil \frac{n}{i} \rceil.
首先观察 F(n-1) = \lceil \frac{n-1}{1} \rceil + \lceil \frac{n-1}{2} \rceil ... + \lceil \frac{n-1}{n-1}\rceil. 比较 F(n) 比其多了 \lceil \frac{n}{n}\rceil 以及原本 i | n-1 的项都比原来大一。所以 F(n) = F(n-1) + \sigma(n) + 1, 其中 \sigma(n)n 的因子数,可以线性筛求出。接着 F(n) 可线性求出。
接着题目中要求的 f(n),容斥可以算出 f(n) = \sum_{d|n} \mu(d) * F(\frac{n}{d}). 另 M(n) = \sum_{i=1}^{n} f(i) = \sum_{i=1}^{n} \sum_{d|i} \mu(d) * F(\frac{i}{d}). 对于每一个 d 而言,有 F(1), F(2) ... F(\lfloor \frac{n}{d} \rfloor) 这几种可能。所以 M(n) = \sum_{d=1}^{n} \mu(d) M(\lfloor \frac{n}{d} \rfloor). 因为在 \lfloor \frac{n}{d} \rfloor 只有 \sqrt{n} 中可能,当处理到 l 时,i \in [l, n / (n / l)](整除) 中 M(\lfloor \frac{n}{i} \rfloor) 是相等的。所以我们还要预处理一下莫比乌斯函数的前缀和即可。整体的复杂度为 O(n + q \sqrt{n}).

当然,其实在推导出 f(n) = \sum_{d|n} \mu(d) * F(\frac{n}{d}) 时,我们就可以递推去做了。做到了 f(i) 时,就把 M(i*k) += \mu(k) * f(i), 这样复杂度是 O(n log n). 然而我鬼迷心窍选择了上面的一种做法。。。。。

再贴一下另一个版本的代码。

 

完结

发表评论

电子邮件地址不会被公开。 必填项已用*标注