知识点: 莫比乌斯反演
原题面：Luogu
扯
感谢 oi-wiki 贡献的今日懵点：
「luogu 3768」简单的数学题
求：
\[\sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot \gcd(i,j)\bmod p\\
n\leq10^{10},5\times10^8\leq p\leq1.1\times10^9,\text{p 是质数}
\]
解法二
转化一下，可以将式子写成
\[\sum_{d=1}^{n}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}ijd\cdot[\gcd(i,j)=1]\]
？这推导给我看懵了，\(d\) 怎么只剩一个了啊
？哪来的 \(m\) 啊
开了个 pr 修了一下。
题意简述
给定参数 \(n\)、\(p\)，求：
\[\left(\sum_{i=1}^n\sum_{j=1}^ni\cdot j\cdot \gcd(i,j)\right)\bmod p
\]
\(n\leq10^{10}\)，\(5\times10^8\leq p\leq1.1\times10^9\)，\(p\in \mathrm{primes}\)。
时限 4s。
分析题意
无脑套路暴力。
考虑先枚举 \(\gcd(i,j)\)，原式等价于：
\[\begin{aligned}
&\sum_{d=1}d\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(i,j)=d]ij\\
=& \sum_{d=1}d\sum_{i=1}^{n}[d|i]\sum_{j=1}^{n}[d|j][\gcd(\dfrac{i}{d},\dfrac{j}{d})=1]ij
\end{aligned}\]
提出 \(d\)，变为枚举 \(\frac{i}{d}\) 与 \(\frac{j}{d}\)，消去整除的条件，原式等价于：
\[\begin{aligned}
&\sum_{d=1}d\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)=1]id\cdot jd\\
=& \sum_{d=1} d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[\gcd(i,j)=1]ij
\end{aligned}\]
代入 \([\gcd(i,j) = 1] = \sum\limits_{d\mid \gcd(i,j)} {\mu (d)}\)，原式等价于：
\[\sum_{d=1} d^3\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}ij\sum_{t|\gcd(i,j)}\mu (t)
\]
值得注意的是 \(t\) 的上界为 \(\frac{n}{d}\)，\(dt\le n\)。
调换枚举顺序，先枚举 \(t\)，原式等价于：
\[\sum_{d=1} d^3\sum_{t=1}\mu(t)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[t|i] \sum_{j=1}^{\left\lfloor\frac{n}{d}\right\rfloor}[t|j]ij
\]
和上面一样，提出 \(t\)，套路地消去整除的条件，原式等价于：
\[\sum_{d=1} d^3\sum_{t=1}\mu(t)t^2\sum_{i=1}^{\left\lfloor\frac{n}{dt}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{dt}\right\rfloor}ij
\]
发现后面两个求和是等差数列乘等差数列的形式。
设 \(g(p,q) = \sum\limits_{i=1}^{p} \sum\limits_{j=1}^{q}ij\)，\(g_{p,q}\) 可以通过下式 \(O(1)\) 计算：
\[g(p,q) = \sum_{i=1}^{p} i \sum_{j=1}^{q}j= \dfrac{(1 + p)\times p}{2}\times \dfrac{(1+q)\times q}{2}
\]
代入原式，原式等价于：
\[\sum_{d=1} d^3\sum_{t=1}\mu(t)t^2\cdot g\left({\left\lfloor\frac{n}{dt}\right\rfloor},{\left\lfloor\frac{n}{dt}\right\rfloor}\right)
\]
考虑枚举 \(T = dt\)，显然 \(T\le n\)。
再考虑枚举 \(d|T\)，即可得到 \(t = \frac{T}{d}\)，原式等价于：
\[\begin{aligned}
&\sum_{T=1}^{n}g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)\sum_{d|T}d^3\mu{\left(\dfrac{T}{d}\right)}\left(\dfrac{T}{d}\right)^2\\
=& \sum_{T=1}^{n}T^2 g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)\sum_{d|T}d\cdot \mu{\left(\dfrac{T}{d}\right)}
\end{aligned}\]
对于后面这一坨，用 \(\sum\limits_{d|T}d\cdot \mu{\left(\frac{T}{d}\right)} = \operatorname{Id} \ast \mu(T)= \varphi(T)\) 反演，则原式等价于：
\[\sum_{T=1}^{n}T^2 \varphi(T) \cdot g\left({\left\lfloor\frac{n}{T}\right\rfloor},{\left\lfloor\frac{n}{T}\right\rfloor}\right)
\]
后半块可以数论分块，考虑前半块。
发现前半段即为 \(\operatorname{Id}^2(T)\varphi(T)\)，又是前缀和形式，考虑杜教筛。
有：
\[f(n) = \operatorname{Id}^2\varphi(n)
\]
考虑找到一个函数 \(g\)，构造函数 \(h = f\ast g\) 使其便于求值，有：
\[h(n) = \sum_{d|n} d^2\varphi(d)\cdot g\left(\dfrac{n}{d}\right)
\]
看到同时存在 \(d\) 和 \(\frac{n}{d}\)，考虑把 \(d^2\) 消去。
令 \(g = \operatorname{Id}^2\)，有：
\[\begin{aligned}
h(n) =& \sum_{d|n} d^2\varphi(d)\cdot \left(\dfrac{n}{d}\right)^2\\
=& n^2\sum_{d|n} \varphi(d)\\
=& n^2 \cdot \varphi \ast 1(n)\\
\end{aligned}\]
又 \(\varphi \ast 1 = \operatorname{Id}\)，则有：
\[h(n) = n^3
\]
找到了合适的 \(g\)，套杜教筛的公式。
\[\begin{aligned}
g(1)S(n) &= \sum_{i=1}^{n}h(i) - \sum_{i=2}^{n}g(i)S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\\
S(n) &= \sum_{i=1}^{n} i^3 - \sum_{i=2}^{n} i^2\cdot S\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)
\end{aligned}\]
前一项是自然数的立方和，有 \(\sum\limits_{i=1}^{n} i^3 = (\frac{n(n+1)}{2})^2\)。证明详见：自然数前n项平方和、立方和公式及证明 - 百度文库。
后一项直接等差数列求和 + 数论分块求解即可。
爆零小技巧
代码实现
代码先咕咕咕咕