一个正整数T表示数据组数

接下来T行 每行两个正整数 表示N、M

T行 每行一个整数 表示第i组数据的结果

版权所有者： 倪泽堃

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mod=1e8+9;11 const int mxn=1e7+3;12 int read(){13     int x=0,f=1;char ch=getchar();14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}16     return x*f;17 }18 int pri[mxn],cnt;19 LL g[mxn],smm[mxn];20 bool vis[mxn];21 void init(){22     g[1]=1;23     for(int i=2;i<mxn;i++){24         if(!vis[i]){25             pri[++cnt]=i;26             g[i]=1-i;27         }28         for(int j=1;j<=cnt && (LL)pri[j]*i<mxn;j++){29             vis[pri[j]*i]=1;30             if(i%pri[j]==0){31                 g[pri[j]*i]=g[i];32                 break;33             }34             g[pri[j]*i]=g[i]*g[pri[j]]%mod;35         }36     }37     for(int i=1;i<mxn;i++)38         smm[i]=(smm[i-1]+g[i]*i%mod)%mod;39     return;40 }41 inline int SS(int x,int y){42     return ((LL)x*(x+1)/2%mod)*((LL)y*(y+1)/2%mod)%mod;43 }44 LL calc(int n,int m){45     if(n>m)swap(n,m);46     LL res=0;int pos;47     for(int i=1;i<=n;i=pos+1){48         int x=n/i,y=m/i;49         pos=min(n/x,m/y);50         res=(res+(smm[pos]-smm[i-1])*(SS(x,y)))%mod;51     }52     return res;53 }54 int n,m;55 int main(){56     freopen("bzoj_2693.in","r",stdin);57     freopen("bzoj_2693.out","w",stdout);58     init();59     int T=read();60     while(T--){61         n=read();m=read();62         printf("%d\n",(calc(n,m)+mod)%mod);63     }64     return 0;65 }