莫比乌斯反演裸题

#include <bits/stdc++.h>
using namespace std;
#define N 51000
#define ll long long 
int prime[N],ip[N],mu[N];
int T,n,m,d,cnt;
ll ans;
void init()
{
    mu[]=;
    for(int i=;i<=;i++)
    {
        if(!ip[i])prime[++cnt]=i,mu[i]=-;
        for(int j=;j<=cnt&&i*prime[j]<=;j++)
        {
            ip[i*prime[j]]=;
            if(i%prime[j]==)break;
            mu[i*prime[j]]=-mu[i];
        }
    }
}
int main()
{
    //freopen("tt.in","r",stdin);
    init();
    for(int i=;i<=;i++)
        mu[i]+=mu[i-];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&d);
        ans=;
        for(int i=,last;i<=n/d&&i<=m/d;i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            ans+=(ll)(n/i/d)*(m/i/d)*(mu[last]-mu[i-]);
        }
        printf("%lld\n",ans);
    }
    return ;
}