首先注意到，对于任意一个1≤i≤k1≤i≤k，⌊ki⌋⌊ki⌋的取值只有O(k−−√)O(k)种，并且相同的⌊ki⌋⌊ki⌋的取值对应的ii都是连续的一段区间。所以，先把所有满足条件的区间提取出来。
对于任意一个⌊ki⌋==⌊ki+1⌋⌊ki⌋==⌊ki+1⌋，有：
k=i∗⌊ki⌋+kmodi=(i+1)∗⌊ki+1⌋+kmod(i+1)k=i∗⌊ki⌋+kmodi=(i+1)∗⌊ki+1⌋+kmod(i+1)
设x=⌊ki⌋,a=kmodix=⌊ki⌋,a=kmodi，则有：
i∗x+a=(i+1)∗x+kmod(i+1)i∗x+a=(i+1)∗x+kmod(i+1)
化简得a=x+kmod(i+1)a=x+kmod(i+1)。
即对于任意一个⌊ki⌋==⌊ki+1⌋⌊ki⌋==⌊ki+1⌋，有kmodi=kmod(i+1)+⌊ki⌋kmodi=kmod(i+1)+⌊ki⌋。
也就是说，对于一段区间[l,r][l,r]，如果⌊kl⌋,⌊kl+1⌋,…,⌊kr−1⌋,⌊kr⌋⌊kl⌋,⌊kl+1⌋,…,⌊kr−1⌋,⌊kr⌋的值全部相同，则有：
∑ri=lkmodi=(kmodl)∗(r−l+1)−⌊kl⌋∗(r−l)∗(r−l+1)2∑i=lrkmodi=(kmodl)∗(r−l+1)−⌊kl⌋∗(r−l)∗(r−l+1)2。
这样就很好做了。具体实现见代码。注意，对于任意一个i>ki>k，kmodi=kkmodi=k。
https://blog.csdn.net/xyz32768/article/details/77809589