BZOJ 2301: [HAOI2011]Problem b (莫比乌斯反演+分块+容斥)

#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int maxn=50000+100;

int mu[maxn],sum[maxn];
bool isprime[maxn];
int prime[maxn],tot;

void init(){
  
  for(int i=0;i<maxn;i++) isprime[i]=true;
  isprime[0]=isprime[1]=false;
  tot=0;
  sum[0]=0;
  sum[1]=mu[1]=1;
  for(int i=2;i<maxn;i++){
    
    if(isprime[i]) prime[tot++]=i,mu[i]=-1;
    for(int j=0;j<tot && i*prime[j]<maxn;j++){
      
      isprime[i*prime[j]]=false;
      if(i%prime[j]) mu[i*prime[j]]=-mu[i];
      else break;
    }
  }
  for(int i=2;i<maxn;i++) sum[i]=sum[i-1]+mu[i];
}

ll Mobius(int a,int b){
  
  if(a>b) swap(a,b);
  int pos;
  ll res=0;
  for(int i=1;i<=a;i=pos+1){
    
    pos=min(a/(a/i),b/(b/i));
    res+=(ll)(sum[pos]-sum[i-1])*(a/i)*(b/i);
  }
  return res;
}

int main(){
  
  int n;
  scanf("%d",&n);
  init();
  while(n--){
    
      int a,b,c,d,k;
      scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
      a--,c--; 
      a/=k;b/=k;
      c/=k;d/=k;
      printf("%lld\n",Mobius(b,d)-Mobius(a,d)-Mobius(b,c)+Mobius(a,c));   
  }
  
}