C++14(g++5.4) 解法, 执行用时: 811ms, 内存消耗: 1244K, 提交时间: 2020-10-09 21:13:31

#include<iostream>
#include<cstdio>
#include<cmath>
#define ll long long
using namespace std;
int p[10000],cnt,mu[50000],n,k,a,b,c,d,sum[50000];
bool isp[50010];
void getp(){
	isp[1]=mu[1]=1;
	for(int i=2;i<=50000;i++){
		if(!isp[i]){
			p[++cnt]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=cnt&&i*p[j]<=50000;j++){
			isp[i*p[j]]=1;
			if(i%p[j]==0) break;
			else mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<=50000;i++) sum[i]=sum[i-1]+mu[i];
}
ll cal(int x,int y,int k){
	int l=1,r=0;
	ll ans=0;
	x/=k;y/=k;
	while(r<min(x,y)){
		r=min(x/(x/l),y/(y/l));
		ans=(ans+(sum[r]-sum[l-1])*1ll*(x/l)*1ll*(y/l))*1ll;
		l=r+1;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	getp();
	while(n--){
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		printf("%lld\n",cal(d,b,k)-cal(d,a-1,k)-cal(c-1,b,k)+cal(c-1,a-1,k));
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 811ms, 内存消耗: 1220K, 提交时间: 2023-01-17 20:05:16

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int mu[maxn],p[maxn],flag[maxn];
void init(){
	int tot=0;
	mu[1]=1;
	for(int i=2;i<maxn;i++){
		if(!flag[i]){
			p[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot&&i*p[j]<maxn;j++){
			flag[i*p[j]]=1;
			if(i%p[j]==0){
				mu[i*p[j]]=0;break;
			}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=1;i<maxn;i++)mu[i]+=mu[i-1];
}
int solve(int n,int m){
	int res=0;
	for(int l=1,r;l<=min(n,m);l=r+1){
		r=min(n/(n/l),m/(m/l));
		res+=(mu[r]-mu[l-1])*(n/l)*(m/l);
	}
	return res;
}
int main(){
	int n;
	int a,b,c,d,k;
	cin>>n;
	init();
	while(n--){
		scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
		printf("%d\n",solve(b/k,d/k)-solve((a-1)/k,d/k)-solve(b/k,(c-1)/k)+solve((a-1)/k,(c-1)/k));
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 996ms, 内存消耗: 13296K, 提交时间: 2023-06-09 18:49:53

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int mu[N],vis[N],sum[N];
vector<ll>prime;
void init()
{
	mu[1]=1;
	for(int i=2;i<N;++i)
	{
		if(!vis[i])
		{
			prime.push_back(i);
			mu[i]=-1;
		}
		for(auto j:prime)
		{
			if(i*j>N)break;
			vis[i*j]=1;
			if(i%j==0)break;
			mu[i*j]=-mu[i];
		}
	}
	for(int i=1;i<N;++i)sum[i]=sum[i-1]+mu[i]; 
}
ll f(int a,int b,int k)
{
	a/=k;b/=k;
	ll ans=0;
	int n=min(a,b);
	for(int l=1,r;l<=n;l=r+1)
	{
		r=min(n,min(a/(a/l),b/(b/l)));
		ans+=(ll)(sum[r]-sum[l-1])*(a/l)*(b/l);
	}
	return ans;	
}
int main()
{
	init();
	int T;
	cin>>T;
	while(T--)
	{
		int a,b,c,d,k;
		cin>>a>>b>>c>>d>>k;
		cout<<f(b,d,k)-f(a-1,d,k)-f(b,c-1,k)+f(a-1,c-1,k)<<'\n';
	}
}