【题解】BZOJ P2301【 [HAOI2011]Problem b】

分析

这里和HDOJ 1695差不多,加个容斥就好了。

代码

#include<cstdio>
#include<algorithm>
using std::fill;using std::swap;
typedef long long int64;
const int MAXN = 50000 + 6;
int primes[MAXN],num,mu[MAXN],sum[MAXN];
bool isPrime[MAXN];
inline int min(int a,int b){return a < b ? a : b;}
void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    num = 0,mu[1] = 1;
    for(int i = 2;i < MAXN;++i){
        if(isPrime[i]) primes[num++] = i,mu[i] = -1;
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < MAXN;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0){
                mu[d] = 0;break;
            }else mu[d] = -mu[i];
        }
    }
    sum[0] = 0;
    for(int i = 1;i < MAXN;i++) sum[i] = sum[i - 1] + mu[i];
}

int64 f(int n,int m,int d){
    if(n > m) swap(n,m);
    int64 ans = 0;
    n /= d,m /= d;
    for(int i = 1,last = 1;i <= n;i = last + 1){
        last = min(n / (n / i),m / (m / i));
        ans += (int64)((sum[last] - sum[i - 1]) * (int64)(n / i) * (int64)(m / i));
    }
    return ans;
}

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    sieve();
    int T,a,b,c,d,k;scanf("%d",&T);
    while(T--){
        scanf("%d %d %d %d %d",&a,&b,&c,&d,&k);
        int ans = f(b,d,k) - f(a - 1,d,k) - f(c - 1,b,k) + f(a - 1,c - 1,k);
        printf("%d\n",ans);
    }

    return 0;
}