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

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

bool vis[maxn];
int mm,mu[maxn],prime[maxn],num[maxn],sum[maxn],d[maxn],sum1[maxn];
void init(){
    mu[1]=1;num[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prime[++mm]=i;
            mu[i]=-1;
            num[i]=2;
            d[i]=1;
        }
        for(int j=1;j<=mm;j++){
            if(prime[j]*i>=maxn)break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                d[i*prime[j]]=d[i]+1;
                num[i*prime[j]]=num[i]/(d[i]+1)*(d[i*prime[j]]+1);
                break;
            }
            else {
                mu[i*prime[j]]=-mu[i];
                d[i*prime[j]]=1;
                num[i*prime[j]]=num[i]*2;
            }
        }
    }
    for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
    for(int i=1;i<maxn;i++)sum1[i]=sum1[i-1]+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[1]=1;num[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            prime[++mm]=i;
            mu[i]=-1;
            num[i]=2;
            d[i]=1;
        }
        for(int j=1;j<=mm;j++){
            if(prime[j]*i>=maxn)break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                d[i*prime[j]]=d[i]+1;
                num[i*prime[j]]=num[i]/(d[i]+1)*(d[i*prime[j]]+1);
                break;
            }
            else {
                mu[i*prime[j]]=-mu[i];
                d[i*prime[j]]=1;
                num[i*prime[j]]=num[i]*2;
            }
        }
    }
    for(int i=1;i<maxn;i++)sum[i]=sum[i-1]+mu[i];
    for(int i=1;i<maxn;i++)sum1[i]=sum1[i-1]+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=0;
        for(int l=1,r;l<=n;l=r+1){
            r=min(n/(n/l),m/(m/l));
            ans+=(sum[r]-sum[l-1])*calc(n/l,m/l);
        }    
        cout<<ans<<'
';
    }
}