jzoj 5842. a
程序员文章站
2024-02-11 13:33:04
...
题目大意:
给定一个n*m 的 01 矩阵,求包含[l,r]个 1 的子矩形个数。
思路:
枚举n的扫描线,然后m是单调的,所以o(n^2*m)轻松出解。
程序:
#include<cstdio>
#include<algorithm>
#include<iostream>
#define N 500005
#define LL long long
LL ans,t,a,b,c,d,k,cnt;
LL sum[N],mu[N],p[N],np[N];
void getmu(LL n){
mu[1]=1;
for (LL i=2;i<=n;i++){
if (!np[i]){
mu[i]=-1;
p[++cnt]=i;
}
for (LL j=1;j<=cnt&&i*p[j]<=n;j++){
np[i*p[j]]=1;
if (i%p[j]==0){
mu[i*p[j]]=0;
break;
}
mu[i*p[j]]=-mu[i];
}
}
sum[1]=1;
for (LL i=2;i<=n;i++) sum[i]=sum[i-1]+mu[i];
}
LL cal(LL n,LL m,LL k){
if (n>m) std::swap(n,m);
LL ans=0,j=0;
for (LL i=1;i<=n/k;i=j+1){
j=std::min(n/(n/i/k)/k,m/(m/i/k)/k);
ans+=(n/i/k)*(m/i/k)*(sum[j]-sum[i-1]);
}
return ans;
}
int main(){
getmu(500000);
scanf("%lld",&t);
while (t){
scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);
ans=cal(b,d,k)-cal(a-1,d,k)-cal(c-1,b,k)+cal(a-1,c-1,k);
printf("%lld\n",ans);
t--;
}
}