P2260 [清华集训2012]模积和
求
\[\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j \]mod 19940417 的值
分析
假设 \(n\le m\)
$\begin{aligned}\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j\end{aligned} $
\(\begin{aligned} & =\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{m} (n \bmod i) \times (m \bmod j)- \sum\limits_{i=1}^{n} (n \bmod i) (m\bmod i)\end{aligned}\)
\(\begin{aligned}=\sum\limits^n_{i=1}(n - \lfloor\dfrac{n}{i}\rfloor i)\sum\limits^m_{j=1}(m-\lfloor\dfrac{m}{j}\rfloor j)-\sum\limits^n_{i=1}(n-\lfloor\dfrac{n}{i}\rfloor i)(m-\lfloor\dfrac{m}{i}\rfloor i)\end{aligned}\)
\(\begin{aligned}=\sum\limits^n_{i=1}(n - \lfloor\dfrac{n}{i}\rfloor i)\sum\limits^m_{j=1}(m-\lfloor\dfrac{m}{j}\rfloor j)-\sum\limits^n_{i=1}(n-\lfloor\dfrac{n}{i}\rfloor i)(m-\lfloor\dfrac{m}{i}\rfloor i)\end{aligned}\)
\(=\left(n^{2}-\sum_{i=1}^{n} i \cdot\left\lfloor\frac{n}{i}\right\rfloor\right) \cdot\left(m^{2}-\sum_{i=1}^{m} i \cdot\left\lfloor\frac{m}{i}\right\rfloor\right)-\sum_{i=1}^{n}\left(n m-m i \cdot\left\lfloor\frac{n}{i}\right\rfloor-n i \cdot\left\lfloor\frac{m}{i}\right\rfloor+i^{2} \cdot\left\lfloor\frac{n}{i}\right\rfloor \cdot\left\lfloor\frac{m}{i}\right\rfloor\right)\)
\(\sum\limits^n_{i=1}i^2=\dfrac{n(n + 1) ( 2n + 1)}{6}\)
加上整除分块、逆元即可
标签：lfloor,right,limits,dfrac,sum,P2260,rfloor,模积,2012 From： https://www.cnblogs.com/CYLSY/p/17066218.html