class="markdown_views prism-atom-one-light">

Description

给出n,m,求
∑i=1n∑j=1,j≠im(nmodi)∗(mmodj)
答案mod 19940417

Solution

转化

看到题目，题意十分简洁，心里十分舒畅。
看到ni就要想到ni=n−⌊ni⌋∗i，然后⌊ni⌋是可以用分块做的，下面再讲。
我们上面的式子可以转化为
∑i=1n∑j=1m(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)−∑i=1min(n,m)(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)
因为我们把所有情况求出来后，还要减去重复的，就是i=j的情况要减去
然后把后面的括号拆开
∑i=1n∑j=1m(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)−∑i=1min(n,m)(nm+i2(⌊ni⌋+⌊mi⌋)−i∗(m∗⌊ni⌋+n∗⌊mi⌋))
然后就

如何分块

我们想有一段区间[l,r]，⌊nl⌋=⌊nr⌋，因为r要求是满足这个条件最大的值，那么就是说⌊nl⌋<=nr，那么就是r<=⌊n⌊nl⌋⌋，因为r是整数，所以还要取整。那么就是[l,r]之间都是满足这个条件的，那么这段区间的答案就可以根据乘法分配律之类的，用⌊nl⌋乘上这段和或者是一些东西就可以了。长练分块打法好，危难来时把命保。

还要注意一个东西

∑i=1ni2=