BZOJ-3994: [SDOI2015]约数个数和

Description

设为x的约数个数，给定N、M，求 输入文件包含多组测试数据。 1<=N, M<=50000 1<=T<=50000。

推式子！！！！
前置技能： 证明显然，不过好像挺难想到。 不妨令n<=m

=
=
=
=
令 则原式=
函数可以在n√n的时间预处理，询问的时候可以按照n/k,m/k分块，预处理前缀和就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n,m;
int mu[51000],pri[51000],cnt;
bool v[51000];
void quick_mu()
{
    mu[1]=1;
    for(int i=2;i<=50000;++i)
    {
        if(!v[i]) pri[++cnt]=i,mu[i]=-1;
        for(int j=1;i*pri[j]<=50000&&j<=cnt;++j)
        {
            v[i*pri[j]]=1;
            if(i%pri[j]) mu[i*pri[j]]=-mu[i];
            else {mu[i*pri[j]]=0; break;}
        }
    }
    for(int i=1;i<=50000;++i) mu[i]+=mu[i-1];
}
ll f[51000];
void quick_f()
{
    for(int i=1;i<=50000;++i)
    {
        int b=1,e;
        while(b<=i)
        {
            e=i/(i/b);
            f[i]+=(ll)(e-b+1)*(i/b);
            b=e+1;
        }
    }
}
int main()
{
    int t; scanf("%d",&t); quick_mu(); quick_f();
    while(t--)
    {
        scanf("%lld%lld",&n,&m); if(n>m) swap(n,m);
        ll b=1,e,ans=0;
        while(b<=n)
        {
            e=min(n/(n/b),m/(m/b));
            ans+=(mu[e]-mu[b-1])*f[n/b]*f[m/b];
            b=e+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}