LOJ#509. 「LibreOJ NOI Round #1」动态几何问题

发布于 2018-04-20  3.1k 次阅读


#509. 「LibreOJ NOI Round #1」动态几何问题

一道好题,我们来一步一步解决它。

首先,我们可以用初中数学的知识,转化一下,发现就是求满足ab为完全平方数的(a,b)的对数。

有多种可能可行的思路,但是最靠谱的还是枚举无平方因子的数然后和完全平方数拼起来。我们可以枚举所有无平方因子的数,那么两边的无平方因子的部分必须一致,剩下的只需保证是完全平方数即可,写一下式子:$$ \sum _{d=1} ^{n} \sqrt{ \lfloor \frac {n}{d} \rfloor } \sqrt{ \lfloor \frac {m}{d} \rfloor }  \mu ^{2} (d) $$

接下来,我们考虑优化这个计算过程,首先可以从mu下手,后面的部分其实就是统计无平方因子的数字的个数。我们可以从容斥的角度考虑,枚举没有i^2这个因子的数的个数,乘上容斥系数,最后就有如下等式成立:

$$\sum _{i=1} ^{n} \mu ^{2} (i) = \sum _{i=1} ^{n^{0.5}} \mu(i) \lfloor \frac {n}{i^{2}} \rfloor $$

之后,问题就转化为杜教筛求出mu的前缀和,之后再分块处理,那么我们就来回忆一下这两个知识点。

首先,杜教筛的套路就是给出一个函数f,求S(n)=∑f(i),同时有另一个比较神奇的函数g,而且f与g的狄利克雷卷积的前缀和比较好求,那么我们就可以转化一下:

$$\sum _{i=1} ^{n} h(i) = \sum _{i=1} ^{n} (g*f) (i) \\ = \sum _{i=1} ^{n} \sum _{d|i} g(d) f(i/d) \\ = \sum _{d=1} ^{n} g(d) \sum _{t=1} ^{n/d} f(t) \\ = \sum _{d=1} ^{n} g(d) S(n/d)$$

之后把第一项拆出来就能做了。

对于除法分块,假设当前的商y=n/x,我们想求y不变的最大的z,那么z=n/y,这样我们就可以得到相同区间的最后一个元素了(有时对于较复杂的式子,一样可以使用这个方法)。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974