P2522 [HAOI2011]Problem b（莫比乌斯反演）

就在例题的基础上加个容斥。注意循环部分不要开long long ，时间会极大幅度的增长。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
typedef long long ll;
int vis[maxn];
int pri[maxn],mu[maxn],sum[maxn],cnt;
void getMu (ll n) {
	mu[1]=1;
	for (ll i=2;i<=n;i++) {
		if (!vis[i]) {
			mu[i]=-1;
			pri[++cnt]=i;
		}
		for (ll j=1;j<=cnt&&i*pri[j]<=n;j++) {
			vis[i*pri[j]]=1;
			if (i%pri[j]==0) break;
			else mu[i*pri[j]]=-mu[i];
		}
	}
	for (ll i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}  
int solve (int a,int b,int d) {
	if (a>b) swap(a,b);
	int ans=0;
	for (ll l=1,r;l<=a;l=r+1) {
		r=min(a/(a/l),b/(b/l));
		ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
	}
	return ans;
} 
main () {
	int _;
	scanf("%d",&_);
	getMu(60000);
	while (_--) {
		int a,b,c,d,e;
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
		int ans=solve(b,d,e)-solve(b,c-1,e)-solve(a-1,d,e)+solve(a-1,c-1,e);
		printf("%lld
",ans);
	}
}