BZOJ 2440 完全平方数(莫比乌斯-容斥原理)

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2440

题意:给定K。求不是完全平方数(这里1不算完全平方数)的倍数的数字组成的数字集合S中第K小的数字是多少?

思路:首先,答案不超过2K,这个我看别人的知道的,我本以为答案会很大。。这样二分就比较显然了。二分之后就是判断可行性。也就是求二分值n之内有多少个集合S中的数字。此时,我们可以反着想,就是计算有多少个数字不是S集合中的,也就是是完全平方数倍数的数字的个数。这个用容斥原理:

(1)加上一个的:n/4+n/9+n/25+……;

(2)减去两个的:n/36+n/100+……;

就是这样,但是这个容斥看起来我觉得复杂付还是蛮大的。下面说莫比乌斯函数:

BZOJ 2440 完全平方数(莫比乌斯-容斥原理)

利用莫比乌斯函数,我们直接求n之内有多少个是S集合中的:

BZOJ 2440 完全平方数(莫比乌斯-容斥原理)

int mou[N];

void init()
{
    i64 i,j;
    for(i=2;i<N;i++) if(!mou[i])
    {
        mou[i]=i;
        for(j=i*i;j<N;j+=i) mou[j]=i;
    }
    mou[1]=1;
    for(i=2;i<N;i++)
    {
        if(i%(mou[i]*mou[i])==0) mou[i]=0;
        else mou[i]=-mou[i/mou[i]];
    }
}

i64 n;

i64 cal(i64 n)
{
    i64 ans=0,i;
    for(i=1;i*i<=n;i++) if(mou[i]) ans+=mou[i]*n/i/i;
    return ans;
}

int main()
{
    init();
    rush()
    {
        RD(n);
        i64 low=1,high=inf,mid,ans;
        while(low<=high)
        {
            mid=(low+high)>>1;
            if(cal(mid)>=n) ans=mid,high=mid-1;
            else low=mid+1;
        }
        PR(ans);
    }
}

上一篇:7 linux服务器程序规范


下一篇:基于 Red5 的流媒体服务器的搭建和应用