求\(\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))\)。