LOJ #2565. 「SDOI2018」旧试题

发布于 2018-05-18  4.3k 次阅读


求\(\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c}d(ijk)\),其中\(a,b,c\leq 10^5\),最多10组数据。

曾经考过这道题的弱化版:26.3.18 考试小记,但是这道题目中给出的标解是\(O(n^2log(n))\)的,在这道题中最多只能拿到30分,上午考试推了半小时推出了这个式子,然后写出来发现由于常数过大只能得到10分= =。之后我一直尝试从式子的角度去优化,但又推了两个多小时发现没有更好的办法。

标解给的很神奇,转化到了图论上,但是我并不会做,而且复杂度也很差。有的人去写了爆搜,好像效果还行,不过复杂度很玄学。

我们可以考虑从数学推导的角度接着搞。首先,无论用什么方法(从二维推到三维或者直接推),我们可以得到答案的式子:

$$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} [(i,j)==1] [(j,k)=1] [(i,k)=1] \lfloor \frac{a}{i} \rfloor \lfloor \frac{b}{j} \rfloor\lfloor \frac{c}{k} \rfloor$$

我们容斥d=gcd(b,c),枚举a,这样还需要保证两组互质关系,写成式子的形式,就是我们最后要的(直接粘的上次写的):

$$\sum_{i=1}^{A} \lfloor \frac{A}{i} \rfloor \sum_{t=1} ^{min(B,C)} \mu(t) [gcd(t,i)=1] \; \sum_{j=1,(i,j)=1} ^{\lfloor \frac{B}{t} \rfloor } \lfloor \frac{B}{jt} \rfloor \; \sum_{k=1,(i,k)=1} ^{\lfloor \frac{C}{t} \rfloor } \lfloor \frac{C}{kt} \rfloor$$

我们考虑如何计算这个东西。最外层的\(i\)是必须直接枚举的,对于内层,显然如果我们能对\(t\)进行分块处理,那么复杂度才是可以接受的。但是这样就需要我们来搞一个前缀和,而前缀和又是与外层的\(i\)相关的,因此我们考虑快速计算这个前缀和。

首先我们定义函数 \( h(x,y)=\sum_{i=1}^{x} [gcd(i,y)=1]  \lfloor \frac{x}{i} \rfloor \),我们的目的就是计算这个玩意。

接着,我们发现在分块过程中,最多只会用到sqrt(n)个h,那么我们可以考虑计算每个单点的h值,先把每个断点的函数值初始化成不管互质关系的前缀和。考虑对\(i\)分解质因数,也就是从小到大枚举i的每一个质因子,那么我们只要从大到小倒序枚举一个断点,令s[pos[x]]-=s[pos[x]/y]即可,这样,由于断点与商的值是等价的,我们将断点的值除掉y,也一定会出现在断点数组里面,就有了一个逐步晒掉所有不符合要求的质因子的递推过程。相似的,对于mu的处理,也是用这种思路,不过要用正序枚举,因为如果原来包含这个因子,现在还包含这个因子,对于mu而言会变成0,而我们的目的其实是去除影响,所以这里要特殊处理。

最后,我们就可以得到符合条件的mu的前缀和以及h值,就可以搞了,时间复杂度\(O(n^{1.5}log(n))\)。

 

 


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