题目链接

题目描述

求∑∑((nmodi)∗(mmodj))其中1<=i<=n,1<=j<=m,i≠j" role="presentation" style="position: relative;">∑∑((nmodi)∗(mmodj))其中1<=i<=n,1<=j<=m,i≠j$\sum \sum ((nmodi)\ast (mmodj))其中1<=i<=n,1<=j<=m,i\ne j$。 例如对于 n=3,m=4 :
答案为(3 mod 1)(4 mod 2)+(3 mod 1) (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1

题解

可以先去做做余数求和 ，我的题解。 一开始看漏了i≠j" role="presentation" style="position: relative;">i≠j$i\ne j$，以为这和余数求和一样…
但是既然又和取模的和有关，与余数求和的思想是差不多的。
我们有amodb=a−floor(a/b)∗b" role="presentation" style="position: relative;">amodb=a−floor(a/b)∗b$amodb=a-floor(a/b)\ast b$
于是我们再来推一波式子:
∑i=1n∑j=1,j≠im((nmodi)∗(mmodj))" role="presentation">∑i=1n∑j=1,j≠im((nmodi)∗(mmodj))$$\sum _{i=1}^n\sum _{j=1,j\ne i}^m((nmodi)\ast (mmodj))$$
=∑∑((nmodi)∗(mmodj))−∑i=1min(n,m)((nmodi)∗(mmodi))" role="presentation" style="position: relative;">=∑∑((nmodi)∗(mmodj))−∑min(n,m)i=1((nmodi)∗(mmodi))$=\sum \sum ((nmodi)\ast (mmodj))-\sum _{i=1}^{min(n,m)}((nmodi)\ast (mmodi))$ 前面那段就是余数求和的方法，不多讲，我们来看后面一段。
不妨设n≤m" role="presentation" style="position: relative;">n≤m$n\le m$
那么:
∑i=1n((nmodi)∗(mmodi))" role="presentation" style="position: relative;">∑ni=1((nmodi)∗(mmodi))$\sum _{i=1}^n((nmodi)\ast (mmodi))$
=∑((n−n/i∗i)∗(m−m/i∗i))" role="presentation" style="position: relative;">=∑((n−n/i∗i)∗(m−m/i∗i))$=\sum ((n-n/i\ast i)\ast (m-m/i\ast i))$
令n/i=x,m/i=y" role="presentation" style="position: relative;">n/i=x,m/i=y$n/i=x,m/i=y$
原式化为:
∑(mn−mxi−nyi+xy∗i2)" role="presentation" style="position: relative;">∑(mn−mxi−nyi+xy∗i2)$\sum (mn-mxi-nyi+xy\ast i^2)$
∑(mn+xy∗i2−(mx+ny)∗i)" role="presentation" style="position: relative;">∑(mn+xy∗i2−(mx+ny)∗i)$\sum (mn+xy\ast i^2-(mx+ny)\ast i)$ 到这里式子已经推的差不多了。
我们发现可以对x,y" role="presentation" style="position: relative;">x,y$x,y$进行除法分块，且前面的mn可以预先处理掉。
于是我们着眼于求出一个块内的(xy∗i2−(mx+ny)∗i)" role="presentation" style="position: relative;">(xy∗i2−(mx+ny)∗i)$(xy\ast i^2-(mx+ny)\ast i)$
假定当前块内