记录编号	143923	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2011] Crash的数字表格	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	6.250 s
提交时间	2014-12-18 19:50:40	内存使用	118.08 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=20101009;
const int SIZE=10000010;
LL miu[SIZE];
LL Section_Endpoint(LL n,LL m,LL i){//n/j!=n/i或m/j!=m/i的第一个j,除法是int意义
	return min(n/(n/i),m/(m/i));
}
LL Sigma_NNS(LL m,LL n){//1~n求和
	return ((m+n)*(n-m+1)/2)%MOD;
}
LL Sigma_RP_Mul(LL a,LL b){//1<=x<=a,1<=y<=b,gcd(x,y)=1的xy求和
	LL ans=0,i=1,j;
	while(i<=a&&i<=b){
		j=Section_Endpoint(a,b,i);
		LL now=(Sigma_NNS(1,a/i)*Sigma_NNS(1,b/i))%MOD;
		now=(now*(miu[j]-miu[i-1]+MOD))%MOD;
		ans=(ans+now)%MOD;
		i=j+1;
	}
	return ans;
}
LL Calc(LL n,LL m){//就是题目让求的那个东西
	LL ans=0,i=1,j;
	while(i<=n&&i<=m){
		j=Section_Endpoint(n,m,i);
		//求解i<=gcd(x,y)<=j的lcm(x,y)之和
		LL now=(Sigma_NNS(i,j)*Sigma_RP_Mul(n/i,m/i))%MOD;
		ans=(ans+now)%MOD;
		i=j+1;
	}
	return ans;
}
void Linear_Sieve_Method(int n){//线性筛!
	static bool flag[SIZE]={0};
	static int ptot=0,p[SIZE];
	for(int i=1;i<=n;i++) miu[i]=1;
	for(int i=2;i<=n;i++){
		if(!flag[i]) p[++ptot]=i,miu[i]=-1;
		for(int j=1;j<=ptot;j++){
			if((LL)i*p[j]>n) break;
			flag[i*p[j]]=true,miu[i*p[j]]=-miu[i];
			if(i%p[j]==0){
				miu[i*p[j]]=0;
				break;
			}
		}
	}
	for(int i=1;i<=n;i++) miu[i]=(miu[i-1]+(LL)i*i*miu[i])%MOD;
}
int main(){
	freopen("nt2011_table.in","r",stdin);
	freopen("nt2011_table.out","w",stdout);
	LL n,m;
	scanf("%lld%lld",&n,&m);
	Linear_Sieve_Method(n);
	printf("%lld\n",Calc(n,m));
	return 0;
}