【BZOJ2301】【HAOI2011】Problem b

  莫比乌斯反演。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=50010;

int Prime[maxn],NotPrime[maxn],mu[maxn],sum[maxn];
int a,b,c,d,k,T;

void Get_MU()
{
	int cnt=0;
	mu[1]=1;
	for (int i=2;i<=maxn;i++)
	{
		if (!NotPrime[i]) {Prime[cnt++]=i;mu[i]=-1;}
		for (int j=0;j<cnt && Prime[j]*i<=maxn;j++)
		{
			NotPrime[i*Prime[j]]=1;
			if (i%Prime[j]==0) break;
			mu[i*Prime[j]]=-mu[i];
		}
	}
	for (int i=1;i<=maxn;i++) sum[i]=sum[i-1]+mu[i];
}

int Calc(int n,int m)
{
	int ans=0,pos;
	if (n>m) swap(n,m);
	for (int i=1;i<=n;i=pos+1)
	{
		pos=min(n/(n/i),m/(m/i));
		ans+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
	}
	return ans;
}

int main()
{
	Get_MU();
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);a--;c--;
		a/=k;b/=k;c/=k;d/=k;
		printf("%d\n",Calc(b,d)+Calc(a,c)-Calc(a,d)-Calc(b,c));
	}
	return 0;
}