●2301 [HAOI2011] Problem b

题链：

http://www.lydsy.com/JudgeOnline/problem.php?id=2301

题解：

莫比乌斯反演,入门题。

类似●HDU 1695 GCD

只是多了一个下界，(另外本题把(a,b)和(b,a)看成两种不同的答案)

把问题拆成四个就好了。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 100500
using namespace std;
int mu[MAXN],pmu[MAXN];
void Mobius_Sieve(){
	static bool np[MAXN]; mu[1]=1; pmu[1]=1;
	static int prime[MAXN],pnt;
	for(int i=2;i<=100000;i++){
		if(!np[i]) prime[++pnt]=i,mu[i]=-1;
		pmu[i]=pmu[i-1]+mu[i];
		for(int j=1;j<=pnt&&i<=100000/prime[j];j++){
			np[prime[j]*i]=1;
			if(i%prime[j]) mu[i*prime[j]]=-mu[i];
			else mu[i*prime[j]]=0;
			if(i%prime[j]==0) break;
		}
	}
}
long long work(int n,int m){
	long long ret=0,tmp;
	for(int i=1,last;i<=min(n,m);i=last+1){
		last=min(n/(n/i),m/(m/i));
		tmp=1ll*(pmu[last]-pmu[i-1])*(n/i)*(m/i);
		ret+=tmp;
	}
	return ret;
}
long long ans(int n,int m,int k){
	return work(n/k,m/k)/*-work(min(n,m)/k,min(n,m)/k)/2*/;
}
int main(){
	Mobius_Sieve(); 
	int a,b,c,d,k,Case; long long ANS;
	scanf("%d",&Case);
	for(int i=1;i<=Case;i++){
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		if(k==0){printf("0
"); continue;}
		//printf("%lld
",ans(b,d,k));
		ANS=ans(b,d,k)-ans(a-1,d,k)-ans(b,c-1,k)+ans(a-1,c-1,k);
		/*
		int dn=max(a,c),up=min(b,d);
		long long _ANS=ans(up,up,k)-ans(dn-1,up,k)-ans(up,dn-1,k)+ans(dn-1,dn-1,k);
		printf("不重复:%lld
",ANS-_ANS/2);
		*/
		printf("%lld
",ANS);
	}
	return 0;
}