HDU-6715 算术(莫比乌斯反演)

$Description$
$\sum_{i=1}^{n}\sum_{j=1}^{m}\mu(lcm(i,j))$
$Solution$
图片说明
$图片说明$

$Code$

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
int prime[N],tot=0,mu[N],n,m;
bool vis[N]={0};
ll h[N];
void pre(){
    mu[1]=1;mu[0]=0;
    for(int i=2;i<N;i++){
        if(!vis[i])prime[++tot]=i,mu[i]=-1;
        for(int j=1;j<=tot&&i*prime[j]<N;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                break;
            }else mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<N;i++)
    for(int j=i;j<N;j+=i)
    h[j]+=mu[i]*mu[j/i];
}
ll f(int T){
    ll ans=0,res=0;
    for(int i=1;i<=n/T;i++)ans+=mu[i*T];
    for(int i=1;i<=m/T;i++)res+=mu[i*T];
    return res*ans;
}
int main(){
    pre();
    int t;cin>>t;
    while(t--){
        scanf("%d%d",&n,&m);
        if(n>m)swap(n,m);
        ll ans=0;
        for(int T=1;T<=n;T++){
            if(mu[T]==0)continue;
            ans+=f(T)*h[T];
        }
        printf("%lld\n",ans);
    }
}