【反演复习计划】【bzoj3994】约数个数和

首先要用数学归纳证明一个结论，不过因为我实在是懒得打公式了...

先发代码吧。

#include<bits/stdc++.h>
#define N 50005
using namespace std;
typedef long long ll;
int prime[N],vis[N],cnt=0,n,m,mu[N];
ll f[N],ans;
void calcmu(){
    mu[1]=1;cnt=0;memset(vis,1,sizeof(vis));
    for(int i=2;i<=N;i++){
        if(vis[i]){prime[++cnt]=i;mu[i]=-1;}
        for(int j=1;j<=cnt;j++){
            int t=i*prime[j];if(t>N)break;
            vis[t]=0;
            if(i%prime[j]==0){mu[t]=0;break;}
            mu[t]=-mu[i];
        }
    }
    for(int n=1;n<=N;n++){
        for(int i=1,j=1;i<=n;i=j+1){
            j=n/(n/i);
            f[n]+=(ll)(j-i+1)*(n/i);
        }
        mu[n]+=mu[n-1];
    }
//    for(int i=1;i<=100;i++)printf("%lld ",f[i]);puts("");
}
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int main(){
    int T=read();calcmu();
    while(T--){
        n=read();m=read();ans=0;if(n>m)swap(n,m);
        for(int i=1,j=1;i<=n;i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans+=1LL*(mu[j]-mu[i-1])*f[n/i]*f[m/i];
        }
        printf("%lld
",ans);
    }
}