[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)

发布于 2018-01-21  90 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)

Description

小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数,然后选取了第 K个数送给了小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗?

Http

BZOJ

Tag

莫比乌斯反演,二分

解决思路

先考虑二分,把题目变成判定问题,即询问在某个范围内,不包含完全平方数因子的数有多少个。
一个数不包含完全平方数,那么就是说唯一分解后没有任何一个质数的质数超过\(1\)。
容斥一下,那么答案就是
Ans-至少一个质因子个数大于1+至少两个质因子个数大于1-至少三个质因子个数大于1-至少四个质因子个数大于1
考虑每一个数对这个式子的贡献,呃,不就是\(\mu()\)吗?
那么线性筛出\(\mu\),二分答案求解就可以啦!

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long

const int maxNum=1000010;
const int inf=2147483647;

int Mu[maxNum];
int pricnt=0,Prime[maxNum];
bool notprime[maxNum];

void GetMu();
ll Check(ll n);

int main()
{
    GetMu();
    int T;scanf("%d",&T);
    while (T--)
    {
        int n;scanf("%d",&n);
        ll l=1,r=1e10,ans;
        do
        {
            ll mid=(l+r)/2;
            if (Check(mid)>=n)//二分判定
                ans=mid,r=mid-1;
            else l=mid+1;
        }
        while (l<=r);
        printf("%lld\n",ans);
    }
    return 0;
}

void GetMu()//线性筛求mu
{
    notprime[1]=1;Mu[1]=1;
    for (int i=2;i<maxNum;i++)
    {
        if (notprime[i]==0) Mu[i]=-1,Prime[++pricnt]=i;
        for (int j=1;(j<=pricnt)&&((ll)i*(ll)Prime[j]<maxNum);j++)
        {
            notprime[i*Prime[j]]=1;
            if (i%Prime[j]==0) break;
            Mu[i*Prime[j]]=-Mu[i];
        }
    }
    return;
}

ll Check(ll n)
{
    ll ret=0;
    for (ll i=1;i*i<=n;i++) ret=ret+Mu[i]*n/i/i;
    return ret;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ2440][中山市选2011]完全平方数(莫比乌斯反演,二分)


HNCJ OIer 一枚