亟隐

朝不闻道,夕亦死可矣

07/14
16:15
数学 算法区

BZOJ 2956: 模积和

地址:戳这里

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}^{m}(n-[\frac{n}{i}]*i)*(m-[\frac{m}{j}]*j)-\sum_{i=1}^{min(n,m)}(n-[\frac{n}{i}]*i)*(m-[\frac{m}{i}]*i)$$

$$=\sum_{i=1}^{n}(n-[\frac{n}{i}]*i)*\sum_{j=1}^{m}(m-[\frac{m}{j}]*j)-\sum_{i=1}^{min(n,m)}(n*m-[\frac{n}{i}]*i*m-[\frac{m}{i}]*i*n+[\frac{n}{i}]*[\frac{m}{i}])$$

代码:戳这里