原题链接
前言：希望大家在做数论题时不应仅仅局限于套路，更应清楚本质。
题意：
记 f(t)=\sum\limits_{k=1}^t k[\gcd(k,t)=1]
求 \sum\limits_{i=1}^n \sum\limits_{j=1}^n (i^2+j^2+ij)f(\gcd(i,j))
首先明显的，要求的式子可以莫比乌斯反演，得到
\sum\limits_{T=1}^n \left(T^2\sum\limits_{d|T}^{}f(d)\mu(T/d)\right) \sum\limits_{i=1}^{\left\lfloor\frac{n}{T}\right\rfloor} \sum\limits_{j=1}^{\left\lfloor\frac{n}{T}\right\rfloor}i^2+j^2+ij
此部分不再赘述。
如果能线性预处理出括号内外的式子，则此题便可数论分块做完。
先看相对简单的后半部分：
记 R(m)=\sum\limits_{i=1}^m \sum\limits_{j=1}^m (i^2+j^2+ij) 也即括号后面的式子。
则
R(m)=2\sum\limits_{i=1}^m i^2+\left(\sum\limits_{i=1}^m i\right)^2=\frac{m(m+1)(2m+1)}{3}+\frac{m^2(m+1)^2}{4}=\dfrac{m(m+1)(11m^2+7m)}{12}
这部分就做完了。
设 g(T)=\sum\limits_{d|T}^{}f(d)\mu(T/d) 最终数论分块时只需乘上 T^2 再做前缀和。
这部分虽然是个狄利克雷卷积形式，但遗憾的是 f(d) 并非积性函数，没法直接线性筛。
先对 f(d) 进行一次莫比乌斯反演：
f(d)=\sum\limits_{k=1}^d k\sum\limits_{i|k,i|d}\mu(i)=\sum\limits_{i|d}^{}\mu(i)\sum\limits_{i|k,1\leq k\leq d}k=\sum\limits_{i|d}\mu(i)i \sum\limits_{k=1}^{d/i}k
设 S(m)=\sum\limits_{i=1}^m i
因此 f(d)=\sum\limits_{i|d}^{}i\mu(i)S(\frac{d}{i})
这还是个狄利克雷卷积，但 S(m)=\frac{m(m+1)}{2} 还不是个积性函数。
可以直接上 狄利克雷生成函数。
对此不十分了解的可先参考这篇文章，或具体数学 \text{Chapter 7} 最后一节（虽然没讲多少但值得挖掘）
先是 S(m) 的 \text{dgf} :
\varrho(z)=\sum\limits_{n\geq 1}^{}\dfrac{S(n)}{n^z}=\dfrac{1}{2} \left(\sum\limits_{n\geq 1}^{}\dfrac{n^2}{n^z}+\sum\limits_{n\geq 1}^{}\dfrac{n}{n^z}\right)=\dfrac{1}{2}\zeta(z-2)+\dfrac{1}{2}\zeta(z-1)
还有 i\mu(i) 的 \text{dgf} ： \psi(z)=\prod\limits_{p\in \text{Prime}}^{}1-\dfrac{p}{p^z}=\prod\limits_{p\in \text{Prime}}^{}1-p^{1-z}=\dfrac{1}{\zeta(z-1)}
所以 f(d) 的 \text{dgf} 就是： \digamma(z)=\varrho(z)\ast \psi(z)=\dfrac{1}{2}+\dfrac{1}
{2}\dfrac{\zeta(z-2)}{\zeta(z-1)}
然而 \varphi(d) 的 \text{dgf} 是： \phi(z)=\dfrac{\zeta(z-1)}{\zeta(z)}
所以 \digamma(z)=\dfrac{1}{2}+\dfrac{1}{2}\phi(z-1),f(d)=[n^{-z}]\digamma(z)=\dfrac{1}{2}\left[d=1\right]+\dfrac{1}{2}d\varphi(d)
这的确出人意料的简洁！
于是我们带到最开始的 g(T) 中：
g(T)=\sum\limits_{d|T}^{}f(d)\mu(T/d)=\dfrac{1}{2}\left(\mu(T)+\sum\limits_{d|T}d\varphi(d)\mu(\frac{T}{d})\right)
再记 h(T)=\sum\limits_{d|T}d\varphi(d)\mu(\frac{T}{d}) 这总算是个积性函数，能线性筛出来了！
对每一个质数 p ,k\geq 2：
\begin{cases}h(1)=1\\h(p)=p\varphi(p)\mu(1)+1\varphi(1)\mu(p)=p^2-p-1\\h(p^2)=p^2(p^2-p)+p(p-1)\cdot(-1)+1\cdot1\cdot0=p^4-p^3-p^2+p\\h(p^k)=p^k(p^k-p^{k-1})-p^{k-1}(p^{k-1}-p^{k-2})=p^{2k}-p^{2k-1}-p^{2k-2}+p^{2k-3}\end{cases}
最后一行后面的因为莫比乌斯函数而没了。
所以线性筛到某个数有多个 p 时特判一下 p^2 ，
其他的由于 h(p^{k+1})=p^2 h(p^k) 直接乘 p^2 就行了。
但这题还有点卡常……
有一个很重要的优化：线性筛 h(T) 时可以开着 \text{long long}不取模。
这是因为其 \text{dgf} 是 \dfrac{\zeta(z-2)}{\zeta(z-1)\zeta(z)}
而 \varphi(n^2) 的 \text{dgf} 是：
\prod\limits_{p\in \text{Prime}}1+\sum\limits_{k\geq 1}^{}\dfrac{\varphi(p^{2k})}{p^{zk}}=\prod\limits_{p\in \text{Prime}}\dfrac{1}{p}+\left(1-\dfrac{1}{p}\right)\sum\limits_{k\geq 0}\dfrac{p^{2k}}{p^{zk}}=\prod\limits_{p\in \text{Prime}}\dfrac{1-p^{1-z}}{1-p^{2-z}}=\dfrac{\zeta(z-2)}{\zeta(z-1)}
由于 \mu(i) 的 \text{dgf} 是 \dfrac{1}{\zeta(z)} ，且 \mu(i)\leq 1
所以 h(T)\leq \varphi(T^2)< T^2 ，不会爆 \text{long long}
代码就不放了。