传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2693
题解见下一篇
Code:
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int maxn=10000005; typedef long long LL; int MOD=100000009; LL n,m; bool p[maxn]; int prime[maxn],minp[maxn]; int u[maxn]; LL f[maxn]; int getint(){ int res=0;char c=getchar(); while(!isdigit(c))c=getchar(); while(isdigit(c))res=res*10+c-'0',c=getchar(); return res; } void init(int maxn){ f[1]=1; for(int i=2;i<maxn;i++){ if(!p[i]){ prime[++prime[0]]=i;minp[i]=i;f[i]=(1-i)%MOD; }for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){ p[i*prime[j]]=1; if(i%prime[j]==0){ minp[i*prime[j]]=minp[i]*prime[j]; f[i*prime[j]]=(LL)(1-prime[j])*f[i*prime[j]/minp[i*prime[j]]]%MOD; break; }else{ minp[i*prime[j]]=prime[j]; f[i*prime[j]]=(LL)f[i]*f[prime[j]]%MOD; } } } for(int i=1;i<maxn;i++)f[i]=(f[i]*i)%MOD; for(int i=2;i<maxn;i++)f[i]=(f[i-1]+f[i])%MOD; } int main(){ init(maxn); int _=getint(); while(_--){ n=getint();m=getint(); LL ans=0; if(n>m)swap(n,m); for(int i=1,last;i<=n;i=last+1){ last=min(n/(n/i),m/(m/i)); LL tmp=(LL)((LL)n/i*(n/i+1)/2%MOD)%MOD*(LL)((LL)m/i*(m/i+1)/2%MOD)%MOD; ans=((LL)(f[last]-f[i-1])%MOD*tmp%MOD+ans)%MOD; }while(ans<0)ans+=MOD; printf("%d\n",ans%MOD); } return 0; }