Neko and function HDU-6537(莫比乌斯

Neko and function HDU-6537

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 50000
#define qc std::ios::sync_with_stdio(false),std::cin.tie(0)
using namespace std;
int n,q,t,prime[MAXN+5],phi[MAXN+5],mo[MAXN+5];
bool isf[MAXN+5];
void iniz_prime(int n){
    memset(isf,true,sizeof(isf));
    phi[1]=1,isf[0]=isf[1]=false,mo[1]=1;
    for (int i=2;i<=n;i++){
        if(isf[i]){
            phi[i]=i-1;
            prime[++prime[0]]=i;
            mo[i]=-1;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++){
            isf[i*prime[j]]=false;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                mo[i*prime[j]]=0;
                break;
            }else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
                mo[i*prime[j]]=-mo[i];
            }
        }
    }
    for(int i=2;i<=n;i++){
        mo[i]+=mo[i-1];
    }
}
int main(){
    qc;
    iniz_prime(MAXN);
    int a,b,d;
    int T;
    cin>>T;
    while (T--)
    {
        cin>>a>>b>>d;
        a/=d,b/=d;
        if(a>b)swap(a,b);
        int ans=0,pos;
        for(int i=1;i<=a;i=pos+1){
            pos=min(a/(a/i),b/(b/i));
            ans+=(mo[pos]-mo[i-1])*(a/i)*(b/i);
        }
        cout<<ans<<"\n";
    }
}