最近脑子炸了，过来做几道数学结论题。很好玩
P3768 简单的数学题
题意
求
\[(\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)\cdot i \cdot j) \bmod p
\]
其中，\(n\le10^{10},p\le 1.1\times10^{10}\) ，\(p\) 是质数
题解
遇事不决，推式子！！！
注：\((i,j)=\gcd(i,j)\)。
\[\begin{align}
\sum_{i=1}^n \sum_{j=1}^n \gcd(i,j)\cdot i \cdot j &= \sum_{x=1}^n x\cdot \sum_{i=1}^n \sum_{j=1}^n [(i,j)=x]\\
&= \sum_{x=1}^n x \cdot \sum_{i=1}^{\lfloor \tfrac{n}{x} \rfloor } \sum_{j=1}^{\lfloor \tfrac{n}{x} \rfloor } i\cdot x\cdot j\cdot x\cdot [(i,j)=1]
\end{align}
\]
我认为这里还是要提一下的。有一个很明显的套路：考虑艾佛森括号，这样就可以把一个难搞的贡献，改成0/1。
然后就是经典的 \([(i,j)=x]\to [(i,j)=1]\) 了，这个是个套路，可以理解为枚举倍数然后判断一下。
后面套个莫比乌斯反演（注释：\([(i,j)=1]=\sum_{d\mid (i,j)} \mu (d)\)）
\[
\begin{align}
\sum_{x=1}^n x \cdot \sum_{i=1}^{\lfloor \tfrac{n}{x} \rfloor } \sum_{j=1}^{\lfloor \tfrac{n}{x} \rfloor } i\cdot x\cdot j\cdot x\cdot [(i,j)=1]&= \sum_{x=1}^n x^3 \cdot \sum_{i=1}^{\lfloor \tfrac{n}{x} \rfloor } \sum_{j=1}^{\lfloor \tfrac{n}{x} \rfloor } i\cdot j\cdot [(i,j)=1]\\&=
\sum_{x=1}^n x^3 \cdot \sum_{i=1}^{\lfloor \tfrac{n}{x} \rfloor } \sum_{j=1}^{\lfloor \tfrac{n}{x} \rfloor } i\cdot j\cdot \sum_{d\mid (i,j)} \mu (d)
\end{align}
\]
套路的，我们考虑把 \(\mu(d)\) 提出来。
\[
\begin{align}
&=\sum_{x=1}^n x^3 \sum_{d=1}^{\lfloor \tfrac{n}{x} \rfloor} \mu(d)
\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} \sum_{j=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i\cdot d\cdot j\cdot d\\
&=\sum_{x=1}^n x^3 \sum_{d=1}^{\lfloor \tfrac{n}{x} \rfloor} \mu(d)
\cdot d^2
\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} \sum_{j=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i\cdot j
\end{align}
\]
我们发现，后面那个只跟 \(i,j\) 的式子并没有什么用，似乎可以用公式优化掉。
\[\begin{align}
\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} \sum_{j=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i\cdot j&=
\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i\sum_{j=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} j\\
&=\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i \cdot \dfrac{\lfloor
\tfrac{n}{xd}
\rfloor (\lfloor \tfrac{n}{xd} \rfloor+1)}{2}\\
&=\dfrac{\lfloor
\tfrac{n}{xd}
\rfloor (\lfloor \tfrac{n}{xd} \rfloor+1)}{2}\cdot
\sum_{i=1}^{{\lfloor \tfrac{n}{xd} \rfloor}} i\\
&=\dfrac{\lfloor
\tfrac{n}{xd}
\rfloor^2 (\lfloor \tfrac{n}{xd} \rfloor+1)^2}{4}
\end{align}
\]
这个式子实在是太不优美了，令 \(t(x)=\dfrac{x^2(x+1)^2}{4}\)。
\[\begin{align}
\sum_{x=1}^n x^3\sum_{d=1}^{\lfloor \tfrac{n}{x}\rfloor} \mu(d)\cdot d^2\cdot t(\lfloor \tfrac{n}{xd}\rfloor)
\end{align}
\]
这个时候又是一个套路了，我们令 \(T=xd\)。
\[\begin{align}
\sum_{T=1}^n \sum_{x\mid T} x^3 \mu(\tfrac{T}{x})\cdot (\tfrac{T}{x})^2\cdot t(\lfloor \tfrac{n}{T}\rfloor)&=
\sum_{T=1}^n T^2 t(\lfloor \tfrac{n}{T}\rfloor ) \sum_{x\mid T} x\cdot \mu(\dfrac{T}{x})
\end{align}
\]
然后发现：
\[\sum_{x\mid T} x\cdot \mu(\dfrac{T}{x})
\]
显然是个狄利克雷卷积的形式啊，就是 \(\mu * id\)。于是我们先推一下这个:
\[\begin{align}
\mu* id&=\mu*(1* \phi)\\
&=(\mu* 1)* \phi \\
&=\epsilon* \phi \\
&=\phi
\end{align}
\]
所以\(\mu * id=\phi\)。
\[\begin{align}
\sum_{T=1}^n T^2 t(\lfloor \tfrac{n}{T}\rfloor ) \sum_{x\mid T} x\cdot \mu(\dfrac{T}{x})&=\sum_{T=1}^n T^2 t(\lfloor \tfrac{n}{T}\rfloor ) \cdot \phi(T)\\
&=\sum_{T=1}^n t(\lfloor \tfrac{n}{T}\rfloor ) \cdot (\phi(T)\cdot T^2)
\end{align}
\]
好，发现十分符合数论分块的口味。对前面那个 \(t\) ，我们数论分块，那么我们想知道 \(\phi(T)\cdot T^2\) 的前缀和。
这个时候杜教筛上了。
令\(f(x)=x^2\phi(x)\)，求 \(s(n)\sum_{i=1}^n f(i)\)
这个时候我们就要构造配合 \(h=f* g\) 的 \(g\) 函数了，既要 \(g(i)\) 好求，还要 \(\sum_{i=1}^n h(i)\) 好求。
观察一下 \(h(n)\)：
\[h(n)=\sum_{d\mid n} d^2\phi(d) g(\tfrac{n}{d})
\]
我么发现，\(d^2\) 是二次的，所以我们的 \(g(x)\) 中也应该含有二次项。那么发现 \(d^2\cdot (\tfrac{n}{d})^2=n^2\)。那么我们不妨令 \(g(i)=i^2\) 试试？
\[\begin{align}
h(n)&=\sum_{d\mid n} d^2\phi(d) g(\tfrac{n}{d})\\
&=\sum_{d\mid n} d^2 \cdot \dfrac{n^2}{d^2} \phi(d)\\
&=n^2\sum_{d\mid n} \phi(d)\\
&=n^3
\end{align}
\]
ok，想想怎么求 \(\sum_{i=1}^n h(i)\)。发现等于 \(\sum_{i=1}^n i^3\)，根据公式，等于\(\dfrac{n^2 (x+1)^2}{4}\)。而 \(\sum_{i=1}^n g(i)=\dfrac{n(n+1)(2n+1)}{6}\)。
所以：
\[s(n)=\dfrac{n^2 (n+1)^2}{4}-\sum_{i=2}^n i^2 s(\lfloor \tfrac{n}{i} \rfloor)
\]
后面那个又一个数论分块。
呼，做完了，好累……