http://www.lydsy.com/JudgeOnline/problem.php?id=2693

 

题解：

考虑把lcm转化成gcd

那答案就是

然后神奇的设：

就有：

一样可以枚举

 的取值，这是O(√n)的；

然后求f(x,y)；

大概证明了一下= =

线性筛之后也可以O(√n)求出f(x,y)

总复杂度O(n)，常数略大。。

这题显然是卡O(n)过不了呗

那就还得优化

预处理这玩意

然后O(√n)就搞出来啦！

设

“积性函数的约数和也是积性函数”  ->好像比较显然?

所以g(D)是积性函数

线性筛裸上就好

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long longconst ll Mod=100000009;ll g[10010005],p[10010005],sum[10010005];bool mark[10010005];ll read(){    ll t=0,f=1;char ch=getchar();    while (ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();}    while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}    return t*f;}void init(){    g[1]=sum[1]=1;    for (ll i=2;i<10010000;i++){        if (!mark[i]){            p[++p[0]]=i;            g[i]=(ll)((i-i*i)%Mod+Mod)%Mod;        }        for (ll j=1;j<=p[0]&&p[j]*i<=10010000;j++){            mark[i*p[j]]=1;            if (i%p[j]==0){                g[i*p[j]]=g[i]*(p[j])%Mod;                break;            }else            g[i*p[j]]=g[i]*g[p[j]]%Mod;        }            sum[i]=sum[i-1]+g[i];    }}ll F(ll x,ll y){    return (((x*(x+1)/2LL)%Mod)*((y*(y+1)/2LL)%Mod))%Mod;}int main(){    init();int T=read();    while (T--){        ll n=read(),m=read();        if (n>m) std::swap(n,m);        ll j;ll ans=0;        for (ll i=1;i<=n;i=j+1){             j=std::min(n/(n/i),m/(m/i));             ans+=((sum[j]-sum[i-1]%Mod+Mod)%Mod)*F(n/i,m/i);             ans%=Mod;        }        printf("%lld\n",ans);    }}