【bzoj2956】模积和

2015年1月12日2,8800

Description

 求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。

Input

第一行两个数n,m。

Output

  一个整数表示答案mod 19940417的值

Sample Input

3 4

Sample Output

1
样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1
数据规模和约定
对于100%的数据n,m<=10^9。

题解

 \[\sum_{i=1}^{n}\sum_{j=1 \land i \not = j}^{m}(n\ mod\ i)(m\ mod\ j)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\sum_{i=1}^{min(n,m)}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{i} \right \rfloor}i)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\]\[\sum_{i=1}^{min(n,m)}(nm+{\left \lfloor \frac{n}{i} \right \rfloor}{\left \lfloor \frac{m}{i} \right \rfloor}i^2-(m{\left \lfloor \frac{n}{i} \right \rfloor}+n{\left \lfloor \frac{m}{i} \right \rfloor})i)\]
推完用上喜闻乐见的分块即可