最近脑子炸了，过来做几道数学结论题。很好玩
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) \]后面那个又一个数论分块。
呼，做完了，好累……
标签：lfloor,cdot,sum,rfloor,几道,xd,tfrac,数学题 From： https://www.cnblogs.com/xmtxlym/p/17933617.html