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

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

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

先发代码吧。

#include<bits/stdc++.h>

#define N 50005

using namespace std;

typedef long long ll;

int prime[N],vis[N],cnt=,n,m,mu[N];

ll f[N],ans;

void calcmu(){

    mu[]=;cnt=;memset(vis,,sizeof(vis));

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

        if(vis[i]){prime[++cnt]=i;mu[i]=-;}

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

            int t=i*prime[j];if(t>N)break;

            vis[t]=;

            if(i%prime[j]==){mu[t]=;break;}

            mu[t]=-mu[i];

        }

    }

    for(int n=;n<=N;n++){

        for(int i=,j=;i<=n;i=j+){

            j=n/(n/i);

            f[n]+=(ll)(j-i+)*(n/i);

        }

        mu[n]+=mu[n-];

    }

//    for(int i=1;i<=100;i++)printf("%lld ",f[i]);puts("");

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    int T=read();calcmu();

    while(T--){

        n=read();m=read();ans=;if(n>m)swap(n,m);

        for(int i=,j=;i<=n;i=j+){

            j=min(n/(n/i),m/(m/i));

            ans+=1LL*(mu[j]-mu[i-])*f[n/i]*f[m/i];

        }

        printf("%lld\n",ans);

    }

}