about 4 years ago

$$这题很早就做过,最近在复习简单数论,因而写个题解,也再试一下 \LaTeX$$

$$[condition]的意思是,如果方括号内的条件为真,则值为1,反之为0.$$


先来看一下我们要求的东西

现在把问题简单化,假设我们已经知道一个质数p,要求

这是个很经典的问题,我们可以用莫比乌斯反演来解决。

如果还不知道莫比乌斯反演,请移步贾志鹏线性筛

$$这个问题我们可以在O(n)-O(\sqrt n)时间内求出$$


由此,我们可以得到一个初步的算法,枚举n以内每个质数p,通过刚刚的方法求出每个质数的答案,然后再加起来。

可是由于多组数据的存在,这个算法很显然是会T的。 我们需要更好的方法。

我们把p加到式子上,看看能不能化简。

以上的p都是质数


上式可以写成

我们假定n < m,有

以上的p也都是质数


现在问题转变为求f(d),令s为d的不相同的质因子个数,由f的定义可知

$$由此,虽然f(d)不是一个积性函数,但我们可以用欧拉筛在线性时间内预处理出所有的f(d).$$

$$我们预处理出f函数后,就能够通过之前的方法实现单组询问O(\sqrt n)的复杂度,总共复杂度就是O(n)-O(\sqrt n)$$

代码网上都有,我就不贴了。具体实现还是挺简单的

[Ahoi2009]chess 中国象棋 →
 
comments powered by Disqus