【BZOJ 2301】[HAOI2011] Problem b

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2301
离线版题目：http://paste.ubuntu.com/20155288/

这个题目和1101简直一毛一样QAQ
就是要减一减。貌似黄学长的做法是容斥一小下。
然而我比较笨，不会容斥。于是就只能暴力搞一搞。
结果一言不合就 Rank 3 QAQ

#include<iostream>
#include<cstdio>
#include<bitset>
using namespace std;

const int MAXN = 50000+9;
const int MX = 50000;

bitset<MAXN> tag;
int pri[MAXN],tot,mu[MAXN],sum[MAXN];

inline int read(){
	char c=getchar(); int buf=0,f=1;
	while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();}
	return buf*f;
}

inline void Get_mu(){
	mu[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!tag[i]) pri[++tot] = i, mu[i] = -1;
		for (int j=1;j<=tot && pri[j]*i<=MX;j++) {
			tag[pri[j]*i] = 1;
			if (i % pri[j]) mu[i*pri[j]] = -mu[i];
			else {mu[i*pri[j]] = 0; break;}	
		}
	}
	for (int i=1;i<=MX;i++) sum[i] = sum[i-1] + mu[i];
}

int main(){
	Get_mu(); int T = read();
	while (T--) {
		int a=read()-1,b=read(),c=read()-1,d=read(),k=read(),vout;
		a /= k; b /= k; c /= k; d /= k; vout = 0;
		for (int i=1,lim=min(b,d),tmp;i<=lim;i=tmp+1){
			tmp = min(b/(b/i),d/(d/i));
			if (a/i) tmp = min(tmp, a/(a/i));
			if (c/i) tmp = min(tmp, c/(c/i));
			vout += (sum[tmp]-sum[i-1])*(b/i-a/i)*(d/i-c/i);
		}
		printf("%d\n",vout);
	}
	return 0;
}