记录编号	452841	评测结果	AAAAAAAAAA
题目名称	[BZOJ 2693] jzptab	最终得分	100
用户昵称	Troywar	是否通过	通过
代码语言	C++	运行时间	26.622 s
提交时间	2017-09-20 14:38:22	内存使用	166.26 MiB

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=100000009ll;
const ll N=(ll)1e7+1;
ll g[N],sum[N];
int prim[N/10],num;
bool vis[N];
inline void init(){
    g[1]=1;
    for(int i=2;i<N;i++){
        if(!vis[i]){
            prim[++num]=i;
            g[i]=1LL*(1-i)*i%mod;
        }
        for(int j=1;i*prim[j]<N;j++){
            vis[prim[j]*i]=true;
            if(i%prim[j])
                g[i*prim[j]]=g[i]*g[prim[j]]%mod;
            else{
                g[i*prim[j]]=g[i]*prim[j]%mod;
                break;
            }
        }
       // printf("g[%d]=%lld\n",i,g[i]);
    }
    for(int i=1;i<N;i++)
        sum[i]=(sum[i-1]+g[i])%mod;
}
inline ll get_S(ll n,ll m){
    return n*(n+1)/2%mod*(m*(m+1)/2%mod)%mod;
}
inline ll solve(ll n,ll m){
    ll ans=0;
    if(n>m) n^=m^=n^=m;
    for(ll i=1,pos;i<=n;i=pos+1){
        pos=min(n/(n/i),m/(m/i));
        ans+=get_S(n/i,m/i)*(sum[pos]-sum[i-1])%mod;
        ans%=mod;
    }
    return (ans%mod+mod)%mod;
}
int main(){
    freopen("bzoj_2693.in","r",stdin);
    freopen("bzoj_2693.out","w",stdout);

    init();
    int T;ll n,m;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",solve(n,m));
    }
}