求

$$\sum_{i=1}^n \sum_{d|i} \lfloor \frac {i}{d + 1} \rfloor$$
交换求和符号得
$$\sum_{d=1}^n \sum_{i=1}^{\lfloor \frac {n}{d}\rfloor} \lfloor \frac {id}{d + 1} \rfloor$$
平移d得
$$\sum_{d=2}^{n+1} \sum_{i=1}^{\lfloor \frac {n}{d-1}\rfloor} \lfloor \frac {id-i}{d } \rfloor$$
将取整符号拆开得

$$\sum_{d=2}^{n+1} \sum_{i=1}^{\lfloor \frac {n}{d-1}\rfloor} i - \lfloor \frac {i}{d} \rfloor - [i \ mod\ d \neq 0]$$
拆开求和，第一项为（设$t = \lfloor \frac {n}{d-1}\rfloor$）

$$\sum_{d=2}^{n+1} \frac {t * (t + 1)}{2}$$
注意到t的取值有根号级别种，用除法分块即可。

第二项为

$$-\sum_{d=2}^{n+1} \sum_{i=1}^{\lfloor \frac {n}{d-1}\rfloor} \lfloor \frac {i}{d} \rfloor$$

内部的和式可以O(1)计算，但还不够。化简一下O(1)计算的式子得到

$$-\sum_{d=2}^{n+1} \frac{1}{2} (\lfloor \frac{n}{d(d-1)} \rfloor-1)(\lfloor \frac{n}{d(d-1)} \rfloor)d+((\lfloor \frac{n}{d-1} \rfloor \ mod \ d) + 1) \lfloor \frac{n}{d(d-1)} \rfloor$$

经过平移d，再设$t = \lfloor \frac {n}{d(d + 1)} \rfloor$，$p=(\lfloor \frac{n}{d} \rfloor \ mod \ (d+1)) + 1$
得到

$$-\sum_{d=1}^{n} \frac{1}{2}t(t-1)(d+1)+tp$$
注意到t再d大于等于根号n时值变成0，所以枚举d到根号n就好了。

第三项为

$$\sum_{d=2}^{n+1} \sum_{i=1}^{\lfloor \frac {n}{d-1}\rfloor}[i \ mod\ d \neq 0]$$
即
$$\sum_{d=2}^{n+1} \lfloor \frac{n}{d+1} \rfloor - \lfloor \frac{n}{d(d+1)} \rfloor$$
注意到前一项可以用除法分块，是根号n的复杂度，后一项d也枚举到根号就可以了。

所以总的复杂度是根号的。