同BZOJ 2154 但是需要优化

$ans=\sum_{d<=n}d*\sum_{i<=\lfloor n/d \rfloor} i^2 *\mu(i)* Sum(\lfloor \frac {n}{i*d} \rfloor,\lfloor \frac {m}{i*d} \rfloor)$

如果我们设$T=i*d$

$ans=\sum_{T<=n} Sum(\lfloor \frac {n}{T}\rfloor,\lfloor \frac {m}{T}\rfloor)\sum_{i \mid T} T*i*\mu(i)$

如果我们能计算出 $\sum_{i \mid T} T*i*\mu(i)$的前缀和 我们就可以在\Theta (n)的时间内解决这个问题

它是积性函数，当$pr[j] \nmid i$的时候，新加入的$pr[j]$对$\mu$没有贡献（均为0）只有$T$的部分发生了改变所以乘一个$pr[j]$就可以了

 

然后就可以$\Theta (T\sqrt n)$解决了

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define md 100000009#define maxn 10000005 int n,m,t,h[maxn],pr[maxn],top=0;bool vis[maxn]; void init(){    memset(vis,false,sizeof vis);    h[1]=1;    F(i,2,maxn-1)    {        if (!vis[i])        {            pr[++top]=i;            h[i]=((i-(ll)i*i)%md+md)%md;        }        F(j,1,top)        {            if ((ll)i*pr[j]>=maxn) break;            vis[i*pr[j]]=true;            if (i%pr[j]==0)            {                h[i*pr[j]]=((ll)h[i]*pr[j])%md;                break;            }            h[i*pr[j]]=((ll)h[i]*h[pr[j]])%md;        }    }    F(i,2,maxn-1)        h[i]=((ll)h[i-1]+h[i])%md;} ll Sum(int n,int m){    n%=md; m%=md;    n=((ll)n*(n+1)/2)%md;    m=((ll)m*(m+1)/2)%md;    return ((ll)n*m)%md;} void solve(int n,int m){    if (n>m) swap(n,m);    ll ret=0;    for (int i=1,last=0;i<=n;i=last+1)    {        last=min(n/(n/i),m/(m/i));        ret=(ret+((ll)h[last]-h[i-1])*Sum(n/i,m/i))%md;    }    ret+=md; ret%=md;    printf("%lld\n",ret);} int main(){    init();    scanf("%d",&t);    while (t--)    {        scanf("%d%d",&n,&m);        solve(n,m);    }}