记录编号	147565	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] Crash的数字表格	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	4.159 s
提交时间	2015-02-02 11:50:22	内存使用	191.05 MiB

#include<iostream>
#include<cstdio>
#define Maxn 10000010
#define LL long long
#define Mod 20101009LL
using namespace std;
int n,m,prime[Maxn],tot=0;
LL r[Maxn],u[Maxn];
LL G(LL n,LL m){
    return ((n*(n+1)/2LL)%Mod)*((m*(m+1)/2LL)%Mod)%Mod;
}
int main(){
	freopen("nt2011_table.in","r",stdin);
	freopen("nt2011_table.out","w",stdout);
	scanf("%d%d",&n,&m);
	if(n<m) swap(n,m);
	r[1]=u[1]=1;
	for(int i=2;i<=n;i++){
		if(!u[i]) r[i]=(Mod-((LL)i*i)%Mod+i)%Mod,prime[++tot]=i;
		for(int j=1;j<=tot&&i*prime[j]<=n;j++){
			u[i*prime[j]]=1;
			if(i%prime[j]==0){r[i*prime[j]]=(LL)prime[j]*r[i]%Mod; break;}
			r[i*prime[j]]=(LL)r[i]*r[prime[j]]%Mod;
		}
	}
	r[0]=0;
	for(int i=1;i<=n;i++) r[i]=(r[i]+r[i-1])%Mod;
	LL ans=0,pos;
	swap(n,m);
	for(LL i=1;i<=n;i=pos+1){
		pos=min(n/(n/i),m/(m/i));
		ans=(ans+(r[pos]-r[i-1]+Mod)%Mod*G(n/i,m/i))%Mod;
	}
	printf("%lld\n",ans);
	return 0;
}