BZOJ2956：模积和

2019-04-13 14:38发布

站内文章 / 模拟电子
10742 0 1132
传送门
  • 题意
    求∑∑((n%i)∗(m%j))(1≤i≤n,1≤j≤m,i!=j)
  • 题解
如果没有i!=j这一条件这道题就简单了。
∑(n%i)=∑(n−⌊ni⌋∗i)=n2−∑(⌊ni⌋∗i) 对于⌊ni⌋相同的区间一起处理即可。
证明：对于任意n，⌊ni⌋的数量级为n√。
因为对于i<n√，i的取值最多n√个，此时区间也不超过n√个，对于i≥n√,⌊ni⌋的取值最多n√个(因为不超过n√)。所以⌊ni⌋的数量级为n√。
加上i!=j这一条件后，将原式变形，得：
∑i=1n∑j=1∨i≠jm((n%i)∗(m%j))=∑i=1n(n%i)∗∑j=1∨i≠jm(m%j)=∑i=1n(n%i)∗∑j=1m(m%j)−∑i=1min(n,m)(n%i)∗(m%i) 对于前面一部分很好处理，对于后面一部分，再进一步变形得
∑i=1min(n,m)(n%i)∗(m%i)=∑

热门文章