【整体二分+莫比乌斯函数+容斥原理】BZOJ2440

【题目大意】

求第k个不是完全平方数或完全平方数整数倍的数。

【思路】

　　由于μ(i)*(n/i^2)=n，可以直接从1开始，得出非完全平方数/完全平方数倍数的数的个数

注意一下二分的写法，这里用的是我一直比较喜欢的一种二分写法：

int lb=下界-1,ub=上界

while (ub-lb>1)

{

　　int mid=(lb+ub)>>1;

　　if (a[mid]>=k) ub=mid; else lb=mid;

}

ans=ub;

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const ll MAXN=+;

 const ll INF=0x7fffffff;

 int T;

 ll k;

 int miu[MAXN];

 ll prime[MAXN];

 int pnum=;

 void get_miu()

 {

     for (int i=;i<MAXN;i++) miu[i]=-INF;

     miu[]=;

     for (int i=;i<MAXN;i++)

     {

         if (miu[i]==-INF)

         {

             miu[i]=-;

             prime[++pnum]=i;

         }

         for (int j=;j<=pnum;j++)

         {

             if (i*prime[j]>=MAXN) break;

             if (i%prime[j]==) miu[i*prime[j]]=;

                 else miu[i*prime[j]]=-miu[i];

         }

     }

 }

 ll square(ll x)

 {

     ll res=;

     for (int i=;i*i<=x;i++) res+=miu[i]*(x/(i*i));

     return res;

 }

 ll get_ans()

 {

     ll lb=-,ub=MAXN*MAXN;

     while (ub-lb>)

     {

         ll mid=(lb+ub)>>;

         ll nowk=square(mid);

         if (nowk>=k) ub=mid;

             else lb=mid;

     }

     return ub;

 }

 int main()

 {

     get_miu();

     scanf("%d",&T);

     for (int i=;i<T;i++)

     {

         scanf("%lld",&k);

         printf("%lld\n",get_ans());

     }

     return ;

 }

巴特西

【整体二分+莫比乌斯函数+容斥原理】BZOJ2440

最新文章

热门文章