## 原始题面

### 题目描述

$\left(\sum_{i=1}^n\sum_{j=1}^n ij \gcd(i,j)\right) \bmod p$

## 解题思路

\begin{aligned} \sum_{i=1}^n\sum_{j=1}^n ij (i,j)&\equiv\sum_{d=1}^nd^3\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor} ij [(i,j)=1]\pmod p\\ &\equiv\sum_{d=1}^nd^3\sum_{e=1}^{\lfloor\frac{n}{d}\rfloor}e^2\mu(e)\sum_{i=1}^{\lfloor\frac{n}{de}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{de}\rfloor} ij\pmod p\\ &\overset{D=de}{\equiv}\sum_{D=1}^n\left({\lfloor\frac{n}{d}\rfloor\left(\lfloor\frac{n}{d}\rfloor+1\right)\over 2}\right)^2D^2\varphi(D)\pmod p\\ \end{aligned}

$$f(n)=n^2\varphi(n)$$, 用杜教筛求 $$S(n):=\sum_{i=1}^nf(i)$$

$$g(n)=n^2$$, 有

\begin{aligned} S(n)=g(1)S(n)&=\sum_{i=1}^n(f*g)(i)-\sum_{i=2}^ng(i)S\left(\left\lfloor\frac{n}{d}\right\rfloor\right)\\ &=\left(\frac{n(n+1)}{2}\right)^2-\sum_{i=2}^ni^2S\left(\left\lfloor\frac{n}{d}\right\rfloor\right) \end{aligned}

## 时间复杂度

$O\left(O(m)+\int_1^{\sqrt n}O\left(\frac{x}{\sqrt m}\right)\mathrm{d}x\right)=O\left(m+\frac{x}{\sqrt m}\right)$

Show code