测试地址：模积和
做法：本题需要用到数论分块。
题目要求的是：∑i=1n∑j=1m[i≠j](n−⌊ni⌋i)(m−⌊mj⌋j)" role="presentation" style="position: relative;">∑ni=1∑mj=1[i≠j](n−⌊ni⌋i)(m−⌊mj⌋j)$\sum _{i=1}^n\sum _{j=1}^m[i\ne j](n-\lfloor \frac{n}{i}\rfloor i)(m-\lfloor \frac{m}{j}\rfloor j)$
也就是：∑i=1n(n−⌊ni⌋i)∑j=1m(m−⌊mj⌋j)−∑i=1min(n,m)(n−⌊ni⌋i)(m−⌊mi⌋i)" role="presentation" style="position: relative;">∑ni=1(n−⌊ni⌋i)∑mj=1(m−⌊mj⌋j)−∑min(n,m)i=1(n−⌊ni⌋i)(m−⌊mi⌋i)$\sum _{i=1}^n(n-\lfloor \frac{n}{i}\rfloor i)\sum _{j=1}^m(m-\lfloor \frac{m}{j}\rfloor j)-\sum _{i=1}^{min(n,m)}(n-\lfloor \frac{n}{i}\rfloor i)(m-\lfloor \frac{m}{i}\rfloor i)$
减号前面那个部分我们在BZOJ1257中讨论过如何用数论分块求了，主要是后面那个部分，我们拆开后发现这个式子等于：
nmmin(n,m)−m∑i=1min(n,m)⌊ni⌋i−n∑i=1min(n,m)⌊mi⌋i+∑i=1min(n,m)⌊ni⌋⌊mi⌋i2" role="presentation" style="position: relative;">nmmin(n,m)−m∑min(n,m)i=1⌊ni⌋i−n∑min(n,m)i=1⌊mi⌋i+∑min(n,m)i=1⌊ni⌋⌊mi⌋i2$nmmin(n,m)-m\sum _{i=1}^{min(n,m)}\lfloor \frac{n}{i}\rfloor i-n\sum _{i=1}^{min(n,m)}\lfloor \frac{m}{i}\rfloor i+\sum _{i=1}^{min(n,m)}\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor i^2$
第一项直接算，第二、三项数论分块，这里只讨论第四项。
我们知道不同的⌊ni⌋" role="presentation" style="position: relative;">⌊ni⌋$\lfloor \frac{n}{i}\rfloor$将区间分成2n" role="presentation" style="position: relative;">2n−−√$2\sqrt{n}$块，那么不同的⌊ni⌋" role="presentation" style="position: relative;">⌊ni⌋$\lfloor \frac{n}{i}\rfloor$和⌊mi⌋" role="presentation" style="position: relative;">⌊mi⌋$\lfloor \frac{m}{i}\rfloor$共同把区间分成了多少块呢？答案是不超过2(n+m)" role="presentation" style="position: relative;">2(n−−√+m−−√)$2(\sqrt{n}+\sqrt{m})$块，证明很容易这里就不讲了，总之也用数论分块算这一块，需要用到∑i=1ni2=n(n+1)(2n+1)6" role="presentation" style="position: relative;">∑ni=1i2=n(n+1)(2n+1)6