洛谷-2522 [HAOI2011]Problem b

  • Post author:
  • Post category:其他



洛谷 2522 [HAOI2011]Problem b

推导一下










f




(


n


,


m


,


k


)


=














i


=


1










n





















j


=


1










m











[


G


c


d




(


i


,


j


)


=


k


]


















F




(


n


,


m


,


k


)


=














i


=


1










n





















j


=


1










m











[


k




|




G


c


d




(


i


,


j


)


]











先不管








f




(


n


,


m


,


k


)












我们先化简








F




(


n


,


m


,


k


)

















F




(


n


,


m


,


k


)


=














i


=


1













n






k
































j


=


1











m






k


















1


=








n






k

























m






k























轻松愉快

然后有








X




=


m


i


n


(


n


,


m


)
















F




(


n


,


m


,


k


)


=














n


k




|




x










X











f




(


n


,


m


,


n


k


)





I


















f




(


n


,


m


,


k


)


=














i


=


1
















X








k























F




(


n


,


m


,


i


k


)





μ


(


i


k


)
















f




(


n


,


m


,


k


)


=














i


=


1
















X








k





























n







i


k


























m







i


k




















μ


(


i


k


)









于是 我们成功将








O


(





n






2










T




)











变成了








O


(


n





T




)












但是 还不够

观察下图



能够看到 许多的














n







i


k























m







i


k


























都是相同的

于是 我们就想办法把相同的合并到一起

对于每一个








i











我们可以通过















m













m







i


k










































求出 最后一个满足














m







i


k


























相同的位置

同时














m







(


i





1


)


k


























的位置我们记下了

那么当前的














m







i


k


























的第一个位置即是 上一个位置+1

另外 凑巧的是 因为














n







i


k























m







i


k


























的值一直相同

所以对于这一连串的














n







i


k























m







i


k




















μ


(


i


k


)










我们只需要求出








μ


(


i


k


)











的前缀和 就可以快速求出这一段的和了

(恐怕看完这一段你都不知道你一开始在求什么了)

附上理解代码

#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
inline int input()
{
    char c=getchar();int o;bool f=0;
    while(c>57||c<48)f|=(c=='-'),c=getchar();
    for(o=0;c>47&&c<58;c=getchar())o=(o<<1)+(o<<3)+c-48;
    return f?-o:o;
}

const int N=50123;
int mu[N],sum[N],prime[N],cnt=0;
bool mark[N];

void GetMu()
{
    int num;
    sum[1]=mu[1]=1;
    for(int i=2;i<=50000;i++)
    {
        if(!mark[i]){mu[i]=-1,prime[++cnt]=i;}
        for(int k=1;k<=cnt;k++)
        {
            num=i*prime[k];
            if(num>N)break;
            mark[num]=1;
            if(i%prime[k]==0){mu[num]=0;break;}
            else mu[num]=-mu[i];
        }
        sum[i]=sum[i-1]+mu[i];
    }
}

int Cal(int a,int b)
{
    if(a>b)swap(a,b);
    int ans=0,pos;
    for(int i=1;i<=a;i=pos+1)\\pos为上一个的末尾位置 当前+1
    {
        pos=min(a/(a/i),b/(b/i));\\要保证一连串都相同 所以取两者之中的更小值
        ans+=(sum[pos]-sum[i-1])*(a/i)*(b/i);
    }
    return ans;
}

int main()
{
    //freopen("In.txt","r",stdin);
    GetMu();
    int T=input(),a,b,c,d,k,res;
    while(T--)
    {
        a=input();b=input();c=input();d=input();k=input();
        a--;c--;
        a/=k;b/=k;c/=k;d/=k;
        res=Cal(a,c)+Cal(b,d)-Cal(a,d)-Cal(b,c);
        printf("%d\n",res);
    }
    return 0;
}



版权声明:本文为qq_37920580原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。