BZOJ 2301

Description:

组数据,每组输入 ,输出


Solution:

首先,根据容斥原理,我们令 表示 时的答案,那么最后所求为 所以我们考虑如何求 (根据对称性,,所以我们可以使得 )

然后莫比乌斯反演有:

但是,时间复杂度过不了。。。这时候我们考虑优化。由于,所以我们考虑用常用技巧,由于的取值只有 个,然后取值相同时 的结果是一样的,我们可以将时间复杂度从 降低到 然后就愉快的 AC 了。

Code:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>

using namespace std;

long long A,B,C,D,K;
int mu[50010]={0};
int hash[50010]={0};
int prime[50010]={0};
int pp=0;

void Pre_()
{
    mu[1]=1;
    for(int i=2;i<=50000;i++)
    {
        if(hash[i]==0)
        {
            prime[++pp]=i;
            mu[i]=-1;
        }
        for(int j=1;j<=pp && i*prime[j]<=50000;j++)
        {
            hash[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
        mu[i]+=mu[i-1];
    }
    return;
}

long long Calc(long long N,long long M)
{
    if(N>M) swap(N,M);
    long long returnd=0;
    int last=0;
    for(int i=1;i<=N;i=last+1)
    {
        long long T1=N/i,T2=M/i;
        last=min(N/T1,M/T2);
        returnd+=(mu[last]-mu[i-1])*T1*T2;
    }
    return returnd;
}

int main()
{
    int T;
    cin>>T;
    Pre_();
    for(;T>0;T--)
    {
        int a,b,c,d,k;
        scanf("%d%d%d%d%d",&a,&c,&b,&d,&k);
        A=a,B=b,C=c,D=d,K=k;
        long long ans=Calc(C/K,D/K)-Calc((A-1)/K,D/K)-Calc(C/K,(B-1)/K)+Calc((A-1)/K,(B-1)/K);
        printf("%lld\n",ans);
    }
    return 0;
}