luogu P3312 [SDOI2014]数表

传送门

我们看要求的东西\[\sum_{i=1}^{n}\sum_{j=1}^{m}[\sigma(gcd(i,j))\le a]\sigma(gcd(i,j))\]

然而\(\le a\)比较烦,可以先去掉这个限制

没有这个限制,我们显然可以枚举每个k,求出gcd为k的数字对数,然后乘上\(\sigma(k)\)再加起来

把这个柿子写出来\[\sum_{k=1}^{min(n,m)}\sigma(k)\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]\]

根据套路,可以得到\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=k]=\sum_{k|d}\mu(\frac{d}{k})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\]

所以原式等于\[\sum_{k=1}^{min(n,m)}\sigma(k)\sum_{k|d}\mu(\frac{d}{k})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\]\[\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{k|d}\sigma(k)\mu(\frac{d}{k})\]

后面那个东西可以枚举倍数,然后求出前缀和,然后直接数论分块救星了

现在加上\(a\)的限制,那么只有\(\le a\)的\(\sigma(k)\)能造成贡献,所以把询问离线,然后按\(a\)排序,依次把满足条件的\(\sigma(k)\)加进前缀和,因为要动态维护前缀和,树状数组即可

#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register

using namespace std;
const int N=1e5+10;
il int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int q,a[N],an[N];
LL prm[N],mu[N],pp[N],xgm[N],tt,ans;
il bool cmp(int a,int b){return xgm[a]<xgm[b];}
int c[N];
il int md(int x){return x&2147483647;}
il void ad(int x,int y){while(x<=N-10) c[x]+=y,x+=x&(-x);}
il int gsm(int x){int an=0;while(x) an+=c[x],x-=x&(-x);return an;}
struct node
{
    int n,m,a,i;
    bool operator < (const node &bb) const {return a<bb.a;}
}qq[N];

int main()
{
    mu[1]=1;
    for(int i=2;i<=N-10;++i)
    {
        if(!pp[i]) pp[i]=1,mu[i]=-1,prm[++tt]=i;
        for(int j=1;j<=tt&&i*prm[j]<=N-10;++j)
        {
            pp[i*prm[j]]=1,mu[i*prm[j]]=-mu[i];
            if(i%prm[j]==0) {mu[i*prm[j]]=0;break;}
        }
    }
    for(int i=1;i<=N-10;++i)
        for(int j=i;j<=N-10;j+=i)
            xgm[j]+=i;
    for(int i=1;i<=N-10;++i) a[i]=i;
    sort(a+1,a+N-10+1,cmp);
    q=rd();
    for(int i=1;i<=q;++i)
    {
        qq[i].n=rd(),qq[i].m=rd(),qq[i].a=rd(),qq[i].i=i;
        if(qq[i].n>qq[i].m) swap(qq[i].n,qq[i].m);
    }
    sort(qq+1,qq+q+1);
    for(int i=1,j=1;i<=q;++i)
    {
        while(j<=N-10&&xgm[a[j]]<=qq[i].a)
        {
            int x=a[j];
            for(int k=1;x*k<=N-10;++k) ad(x*k,xgm[x]*mu[k]);
            ++j;
        }
        int n=qq[i].n,m=qq[i].m,ii=qq[i].i;
        for(int k=1,l;k<=n;k=l+1)
        {
            l=min(n/(n/k),m/(m/k));
            an[ii]=an[ii]+(gsm(l)-gsm(k-1))*(n/k)*(m/k);
        }
    }
    for(int i=1;i<=q;++i) printf("%d\n",md(an[i]));
    return 0;
}