bzoj2440完全平方数

题目链接

上来先吐槽题面！！！！！！

你跟我说$1$不是完全平方数昂？

看了半天样例啊。

活生生的半天$……$

莫比乌斯 反演    函数容斥一下，每次二分就好

反正本宝宝不知道反演是啥。

每次判断应该是

$$\sum^{ \lfloor \sqrt{x} \rfloor}_{i=1} \frac{x}{i^{2}}*\mu(x)$$

然后二分就好，

打表得出上界，之后就没了

/**************************************************************

    Problem: 2440

    User: zhangheran

    Language: C++

    Result: Accepted

    Time:4648 ms

    Memory:6560 kb

****************************************************************/

#include<iostream>

#include<cstdio>

#include<algorithm>

//#include"suqingnian.h"

using namespace std;

    int mu[];

    const int __n=;

    bool __check[];

    int __size;

    int _num[];

    void _prime()

    {

      for(int _i=;_i<=__n;_i++)

        {

          if(!__check[_i]) _num[++__size]=_i,mu[_i]=-;

          for(int _j=;_j<=__size;_j++)

          {

            if(_i*_num[_j]>=__n) break;

            __check[_num[_j]*_i]=;

            if(_i%_num[_j]==) {mu[_i*_num[_j]]=;break;}

            mu[_i*_num[_j]]=mu[_i]*mu[_num[_j]];

          }

        }

        mu[]=__check[]=;

      return ;

    }

//    bool _isprime(int __n) {return ~__check[__n];}

int t;

long long k;

long long calc(long long x)

{

    long long sum=;

    for(long long i=;i*i<=x;i++)

      sum+=x/(i*i)*mu[i];

//  printf("%lld %lld\n",x,sum);

    return sum;

}

//long long che(long long l,long long r,long long)

//{

//

//}

long long hint(long long x)

{

    long long ans=;

    long long l=x,r=;

    while(l<=r){

//      printf("%lld %lld\n",l,r);

        long long mid=l+r>>;

//      printf("%lld \n",calc(mid));

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

        else l=mid+;

    }return ans;

}

int main()

{

    scanf("%d",&t);

    _prime();

    while(t--)

    {

        scanf("%lld",&k);

        printf("%lld\n",hint(k));

    }

}