[BZOJ2956]模积和（数论）

2019-04-13 16:54发布

站内文章 / 模拟电子
14684 0 1482

题目描述

传送门

题解

这题就是正儿八经的化（画）式（柿）子
首先计算i=j和i≠j的总和
ans1=∑i=1n∑j=1m(n mod i)∗(m mod j)
=∑i=1n∑j=1m(n−⌊ni⌋i)∗(m−⌊mj⌋j)
=∑i=1n∑j=1m(nm−n⌊mj⌋j−m⌊ni⌋i+⌊ni⌋i⌊mj⌋j)
=n2m2−n2∑j=1m⌊mj⌋j−m2∑i=1n⌊ni⌋i+∑i=1n⌊ni⌋i∑j=1m⌊mj⌋j
然后计算i=j的情况
令Min=min(n,m)
ans2=∑i=1Min(n mod i)∗(m mod i)
=∑i=1Min(n−⌊ni⌋i)∗(m−⌊mi⌋i)
=∑i=1Min(nm−n⌊mi⌋i−m⌊ni⌋i+

热门文章