欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

jzoj 5842. a

程序员文章站 2024-02-11 13:33:04
...

题目大意:

给定一个n*m 的 01 矩阵,求包含[l,r]个 1 的子矩形个数。
jzoj 5842. a

思路:

枚举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--;
    }
}
相关标签: 何嘉阳

上一篇: 前端(四)

下一篇: dowhy学习1