BZOJ_2956_模积和_数学

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-i*lfloor n/i floor)*(m-j*lfloor m/j floor)
-sum_{i=1}^{n}(n;mod;i)*(m;mod;i)=$$
$$(sum_{i=1}^{n}n-i*lfloor n/i floor;)*(sum_{i=1}^{m}m-i*lfloor m/i floor)-$$
$$sum_{i=1}^{n}(n*m-i*lfloor n/i floor*m-i*lfloor m/i floor*n+
i*lfloor n/i floor*i*lfloor m/i floor)=$$
$$(n^{2}-sum_{i=1}^{n}i*lfloor n/i floor)
*(m^{2}-sum_{i=1}^{m}i*lfloor m/i floor)-$$
$$sum_{i=1}^{n}(n*m-i*lfloor n/i floor*m-i*lfloor m/i floor*n+
i*lfloor n/i floor*i*lfloor m/i floor)$$
两边都能在$sqrt n$的时间内算出

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
ll mod=19940417*6;
ll sum1(ll x) {
	return (x+1)*x%mod/2;
}
ll sum2(ll x) {
	return x*(x+1)%mod*(2*x+1)%mod/6;
}
ll calc1(ll n) {
	int i,lst;
	ll ans=n*n%mod;
	for(i=1;i<=n;i=lst+1) {
		lst=(n/(n/i));
		ans=(ans-(n/i)*(sum1(lst)-sum1(i-1)+mod)%mod+mod)%mod;
	}
	return ans;
}
ll calc2(ll n,ll m) {
	int i,lst;
	ll ans=n*m%mod,r=min(n,m);
	ans=ans*r%mod;
	for(i=1;i<=r;i=lst+1) {
		lst=min(n/(n/i),m/(m/i));
		ll del=(sum1(lst)-sum1(i-1)+mod)%mod;
		ans=(ans-m*(n/i)%mod*del%mod-n*(m/i)%mod*del%mod+(n/i)*(m/i)%mod*(sum2(lst)-sum2(i-1)+mod)%mod)%mod;
	}
	return ans;
}
int main() {
	ll n,m;
	scanf("%lld%lld",&n,&m);
	printf("%lld
",(calc1(n)*calc1(m)%mod-calc2(n,m)+mod)%(mod/6));
}