莫比乌斯反演+模板

链接https://www.lydsy.com/JudgeOnline/problem.php?id=2301

#include<iostream>
#include<cstring>
#include<string>
#define FO(n) for(int i=1;i<=(n);i++)
#define FOR(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define ll long long
#define maxn 50000
using namespace std;
ll mu[maxn+5];
int a,b,c,d,k,n,m;
void get_mu(){//利用欧拉筛推出mu数组
    int isp[maxn+5],prime[maxn+5];
    memset(isp,1,sizeof(isp));
    prime[0]=0,isp[1]=0,mu[1]=1;
    for(int i=2;i<=maxn;i++){
        if(isp[i]){
            mu[i]=-1;
            prime[++prime[0]]=i;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=maxn;j++){
            isp[i*prime[j]]=0;
            if(!(i%prime[j])){
                mu[i*prime[j]]=0;
                break;
            }
            else{               
                mu[i*prime[j]]=-mu[i];
            }
        }
        mu[i]+=mu[i-1];
    }
}
ll cal(int x,int y){//分块
    if(x>y)swap(x,y);
    ll ans=0;
    for(int i=1,last;i<=x;i=last+1){
        last=min(x/(x/i),y/(y/i));
        ans+=(ll)(mu[last]-mu[i-1])*(x/i)*(y/i);
    }
    return ans;
}
int main(){
    int t;
    get_mu();
    cin>>t;
    while (t--)
    {
        cin>>a>>b>>c>>d>>k;
        cout<<
        cal(b/k, d/k)-cal(b/k, (c-1)/k)-cal((a-1)/k, d/k)+cal((a-1)/k, (c-1)/k)
        <<"\n";
    }
}