约数个数求和+线性筛约数——bzoj3994

这题首先要会线性筛约数个数，并求出前缀和

bool vis[maxn];

int mm,mu[maxn],prime[maxn],num[maxn],sum[maxn],d[maxn],sum1[maxn];

void init(){

    mu[]=;num[]=;

    for(int i=;i<maxn;i++){

        if(!vis[i]){

            prime[++mm]=i;

            mu[i]=-;

            num[i]=;

            d[i]=;

        }

        for(int j=;j<=mm;j++){

            if(prime[j]*i>=maxn)break;

            vis[i*prime[j]]=;

            if(i%prime[j]==){

                mu[i*prime[j]]=;

                d[i*prime[j]]=d[i]+;

                num[i*prime[j]]=num[i]/(d[i]+)*(d[i*prime[j]]+);

                break;

            }

            else {

                mu[i*prime[j]]=-mu[i];

                d[i*prime[j]]=;

                num[i*prime[j]]=num[i]*;

            }

        }

    }

    for(int i=;i<maxn;i++)sum[i]=sum[i-]+mu[i];

    for(int i=;i<maxn;i++)sum1[i]=sum1[i-]+num[i];

}

然后通过转化 d(i*j) 化简原式即可

#include<bits/stdc++.h>

using namespace std;

#define maxn 500005

#define ll long long

bool vis[maxn];

int mm,mu[maxn],prime[maxn],num[maxn],sum[maxn],d[maxn],sum1[maxn];

void init(){

    mu[]=;num[]=;

    for(int i=;i<maxn;i++){

        if(!vis[i]){

            prime[++mm]=i;

            mu[i]=-;

            num[i]=;

            d[i]=;

        }

        for(int j=;j<=mm;j++){

            if(prime[j]*i>=maxn)break;

            vis[i*prime[j]]=;

            if(i%prime[j]==){

                mu[i*prime[j]]=;

                d[i*prime[j]]=d[i]+;

                num[i*prime[j]]=num[i]/(d[i]+)*(d[i*prime[j]]+);

                break;

            }

            else {

                mu[i*prime[j]]=-mu[i];

                d[i*prime[j]]=;

                num[i*prime[j]]=num[i]*;

            }

        }

    }

    for(int i=;i<maxn;i++)sum[i]=sum[i-]+mu[i];

    for(int i=;i<maxn;i++)sum1[i]=sum1[i-]+num[i];

}

ll n,m;

inline ll calc(ll n,ll m){return (ll)sum1[n]*sum1[m];}

int main(){

    init();

    int t;cin>>t;

    while(t--){

        cin>>n>>m;

        if(n>m)swap(n,m);

        ll ans=;

        for(int l=,r;l<=n;l=r+){

            r=min(n/(n/l),m/(m/l));

            ans+=(sum[r]-sum[l-])*calc(n/l,m/l);

        }

        cout<<ans<<'\n';

    }

}