记录编号	232614	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2693] jzptab	最终得分	100
用户昵称	zys	是否通过	通过
代码语言	C++	运行时间	21.628 s
提交时间	2016-03-02 12:05:59	内存使用	245.42 MiB

#define MAXT 10010
#define ll long long
#define MAXN 10000010
#define Min(a,b)((a)<(b)?(a):(b))
#define Max(a,b)((a)>(b)?(a):(b))

#include<cstdio>

using namespace std;

const ll Mod=100000009;bool vis[MAXN];
ll Case,n[MAXT],m[MAXT],p[MAXN>>4],mu[MAXN],sum[MAXN],MAX,tot,Ans,Mul[MAXN];

inline void get_p()
{
	sum[1]=1;mu[1]=1;Mul[1]=1;
	for(ll i=2;i<=MAX;i++){
		if(!vis[i])p[++tot]=i,mu[i]=-1,sum[i]=(i-i*i)%Mod;
		for(ll j=1;j<=tot&&(i*p[j])<=MAX;j++){
			vis[p[j]*i]=true;
			if(!(i%p[j])){
				mu[i*p[j]]=0;
				sum[i*p[j]]=(sum[i]*p[j])%Mod;
				break;
			}
			mu[i*p[j]]=-mu[i];
			sum[i*p[j]]=(sum[i]*sum[p[j]])%Mod;
		}
		Mul[i]=(i*(i+1)/2)%Mod;
	}
	for(ll i=2;i<=MAX;i++)sum[i]=(sum[i]+sum[i-1])%Mod;
}

inline void get_ans(ll now)
{
	ll last=0;Ans=0;
	for(ll i=1,r=Min(n[now],m[now]);i<=r;i=last+1){
		last=Min(n[now]/(n[now]/i),m[now]/(m[now]/i));
		Ans=(Ans+(sum[last]-sum[i-1])*Mul[n[now]/i]%Mod*Mul[m[now]/i])%Mod;
	}
	printf("%lld\n",(Ans%Mod+Mod)%Mod);
}

int main()
{
    freopen("bzoj_2693.in","r",stdin);
	freopen("bzoj_2693.out","w",stdout);
	scanf("%lld",&Case);
	for(ll i=1;i<=Case;i++){
		scanf("%lld%lld",&n[i],&m[i]);
		MAX=Max(Max(n[i],m[i]),MAX);
	}
	get_p();for(ll i=1;i<=Case;i++)get_ans(i);
}