bzoj2956 模积和 （分块）

2019-04-13 16:56发布

站内文章 / 模拟电子
15623 0 1641

bzoj2956 模积和

原题地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2956 题意：
求∑∑((n mod i)*(m mod j))，其中1<=i<=n,1<=j<=m,i≠j。答案 mod 19940417 数据范围
n,m<=10^9 题解：
∑ni=1∑mj=1((n mod i)∗(m mod j))   (i≠j)
=∑ni=1∑mj=1((n mod i)∗(m mod j))−∑min(n,m)i=1((n mod i)∗(m mod i)) 前一部分
=∑ni=1∑mj=1((n−i∗⌊ni⌋)∗(m−j∗⌊mj⌋))
=∑ni=1(n−i∗⌊ni⌋)∑mj=1(m−j∗⌊mj⌋)
可以分块做。 后一部分=∑min(n,m)i=1((n mod i)∗(m mod i))
=∑min(n,m)i=1((n−i∗⌊ni⌋)∗(m−i∗⌊mi⌋))
=∑min(n,m)i=1(n∗m−i∗⌊ni⌋∗m−i∗⌊mi⌋∗n+i2⌊mi⌋⌊ni⌋)
也可以分块做。 其中用到了 1+2+..+n=(1+n)∗n2
和12+22+..+n2=n∗(1+n)∗(2n+1)6

热门文章