情形一：$z$的虚部不为$0$（z不是实数）
首先考虑复数这一部分，设$n=(a+bi)(c+di)=ac-bd+(ad+bc)i$
则有$ad+bc=0$，设$\frac{a}{b}=-\frac{c}{d}=\frac{p}{q}$，其中$gcd(p,q)=1$，那么有
$n=x(p+qi)y(p-qi)=xy(p^2+q^2)$，其中$a=px,c=py$
由于$z|n$，所以$z=(p+qi)或(p-qi)$，不妨设$z=(p+qi)$，另一种情况是一样的，最后答案乘2就行了
因此一对$(p,q)$对答案有贡献当且仅当$p^2+q^2|n$，且贡献为$\sum_{x|\frac{n}{p^2+q^2}}px=p \sigma(\frac{n}{p^2+q^2})$（$\sigma(n)表示n的约数之和$）
$LHS=\sum_{i=1}^{n}\sum_{p^2+q^2|n}p \sigma(\frac{i}{p^2+q^2})[gcd(p,q)==1]$
$=\sum_{i=1}^{n}\sum_{k|i}\sigma(\frac{i}{k})\sum_{p^2+q^2=k}p[gcd(p,q)==1]$
$=\sum_{k=1}^{n}\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sigma(i)\sum_{p^2+q^2=k}p[gcd(p,q)==1]$
$=\sum_{k=1}^{n}\sum_{p^2+q^2=k}pD(\left\lfloor\frac{n}{k}\right\rfloor)[gcd(p,q)==1]$（$D(n)表示\sigma(n)的前缀和$）
下底分块枚举，问题就只剩下求$D(n)$，$f(n)=\sum_{p^2+q^2=n}p[gcd(p,q)==1]$及其前缀和$F(n)=\sum_{p^2+q^2<=n}p[gcd(p,q)==1]$
对于$D(n)$，我们有$D(n)=\sum_{i=1}^{n}\sigma(i)=\sum_{i=1}^{n}\sum_{k|i}k=\sum_{k=1}^{n}k\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}1=\sum_{k=1}^{n}k\left\lfloor\frac{n}{k}\right\rfloor$
这个显然可以$O(\sqrt n)$计算
对于$F(n)$，我们考虑消除$p,q$互质的限制：设$G(n)=\sum_{p^2+q^2<=n}p=\sum_{p=1}^{\sqrt n}p\sqrt{n-p^2}$
枚举$d=gcd(p,q)$得到：$F(n)=G(n)-\sum_{d=2}^{\sqrt n}F(\left\lfloor\frac{n}{d^2}\right\rfloor)d$
两者都可以在$O(\sqrt{n})$的时间内计算
利用杜教筛的思想预处理前$n^{\frac{2}{3}}$的值可以做到$O(n^{\frac{2}{3}}\log n)$
情形二：$z$的虚部不$0$（z是实数）
这种情况下$LHS=\sum_{i=1}^{n}\sum_{k|i}k=D(n)$
两种情况加起来就行了
|
|