BZOJ 2956 模积和

发表于 | 更新于

Link

打表大法吼

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
typedef long long ll;
const int P=19940417,inv2=9970209,inv6=3323403;
using std::swap;
using std::min;
ll mul(ll a,ll b){return a*b%P;}
ll SumE(ll a,ll d,ll n){return mul(mul((a+(a+mul(d,n-1))%P)%P,n),inv2);}
ll SumS(ll n){return mul(mul(n,mul(n+1,2*n+1)),inv6);}
ll SumS(int i,int j){return ((SumS(j)-SumS(i-1))%P+P)%P;}
ll f(int n)
{
	ll res=0;
	for(int i=1,last;i<=n;i=last+1)
	{
		last=n/(n/i);
		(res+=SumE(n%last,n/i,last-i+1))%=P;
	}
	return res;
}
ll g(int n,int m)
{
	ll res=mul(mul(n,m),m);
	for(int i=1,last;i<=m;i=last+1)
	{
		last=min(n/(n/i),m/(m/i));
		res+=mul(mul(n/i,m/i),SumS(i,last));res%=P;
		res-=mul(mul(n,m/i),SumE(i,1,last-i+1));((res%=P)+=P)%=P;
		res-=mul(mul(m,n/i),SumE(i,1,last-i+1));((res%=P)+=P)%=P;
	}
	return res;
}
int main()
{
	int n,m;get(n),get(m);
	if(n<m) swap(n,m);
	int Ans=((f(n)*f(m)%P-g(n,m))%P+P)%P;
	put(Ans),putchar('\n');
	return 0;
}