BZOJ2440 中山市选2011完全平方数（容斥原理+莫比乌斯函数）

时间：2023-03-09 18:36:02
BZOJ2440 中山市选2011完全平方数（容斥原理+莫比乌斯函数）

　　如果能够知道不大于n的合法数有多少个，显然就可以二分答案了。

　　考虑怎么求这个。容易想到容斥，即枚举完全平方数。我们知道莫比乌斯函数就是此种容斥系数。筛出来就可以了。

　　注意二分时会爆int。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define inf 2000000000

int T,n,prime[N],mobius[N],cnt=;

bool flag[N];

int calc(int n)

{

    int s=n;

    for (int i=;i*i<=n;i++)

    s+=mobius[i]*(n/(i*i));

    return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj2440.in","r",stdin);

    freopen("bzoj2440.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    flag[]=;mobius[]=;

    for (int i=;i<=N-;i++)

    {

        if (!flag[i]) prime[++cnt]=i,mobius[i]=-;

        for (int j=;j<=cnt&&prime[j]*i<=N-;j++)

        {

            flag[prime[j]*i]=;

            if (i%prime[j]==) break;

            mobius[prime[j]*i]=-mobius[i];

        }

    }

    T=read();

    while (T--)

    {

        n=read();

        unsigned int l=,r=inf;int ans;

        while (l<=r)

        {

            int mid=l+r>>;

            if (calc(mid)>=n) ans=mid,r=mid-;

            else l=mid+;

        }

        cout<<ans<<endl;

    }

    return ;

}

相关文章