Description

求∑i=1n∑j=1,j≠im(nmodi)∗(mmodj)
n,m<=10^9，答案模19940417

Solution

首先，看到有%，心里很不爽，把它变成n−⌊ni⌋∗i，对于i≠j的情况，后面减去就可以了。我们设n<m
于是原式就变成了
∑i=1n∑j=1m(n−⌊ni⌋∗i)∗(m−⌊mj⌋∗j)−∑i=1n(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)
再设f(n)=∑i=1nn−⌊ni⌋∗i
于是原式就变成了f(n)∗f(m)−∑i=1n(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)
考虑分成两部分计算

Part 1

f(n)=∑i=1nn−⌊ni⌋∗i
=n2−∑i=1n⌊ni⌋∗i
发现⌊ni⌋最多只有n√种取值，于是我们可以使用分块。（分块大法好！）
设l为一段连续的⌊ni⌋相等的左端点，那么这个区间的右端点r便满足nr>=⌊nl⌋，并且为最大值。移项得r=⌊n⌊nl⌋⌋。那就可以利用高斯求和搞出来了。

Part 2

∑i=1n(n−⌊ni