Luogu

BZOJ

分析

ZAP这题是一样的。

只是最后要容斥一下,答案是$Ans(b,d)-Ans(a-1,d)-Ans(b,c-1)+Ans(a-1,c-1)$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

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

const int MAXN=50000+10;

int miu[MAXN],v[MAXN],sum[MAXN];
inline void getMiu(int n) {
    for (re int i=1;i<=n;++i) miu[i]=1,v[i]=0;
    for (re int i=2;i<=n;++i) {
        if (v[i]) continue;
        miu[i]=-1;
        for (re int j=i<<1;j<=n;j+=i) {
            v[j]=1;
            if ((j/i)%i==0) miu[j]=0;
            else miu[j]*=-1;
        }
    }
}

inline long long calc(int n,int m) {
    if (n>m) swap(n,m);
    long long ans=0;
    for (re int l=1,r;l<=n;l=r+1) {
        r=min(n/(n/l),m/(m/l));
        ans+=1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]);
    }
    return ans;
}

int main() {
    getMiu(50001);
    for (re int i=1;i<=50001;++i) sum[i]=sum[i-1]+miu[i];
    int T=read();
    while (T--) {
        int a=read(),b=read(),c=read(),d=read(),k=read();
        printf("%lld\n",calc(b/k,d/k)-calc(b/k,(c-1)/k)-calc((a-1)/k,d/k)+calc((a-1)/k,(c-1)/k));
    }
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 15 PM