自己写的第一个博客。。。。。。。。。

BZOJ 2440

【题意】

　　求第K个约数不含平方数的数 （1<=k<=10^9），

　　共有T组数据（T<=50）。

【题解】

　　首先题解并不是我独立思考的结果（我是蒟蒻qwq）。。。

　　设f（n）表示小于等于n的满足所求数性质的数的个数，显然满足单调性，所以可以考虑二分答案吧。

　　然后考虑求出f（n）。

　　怎么求呢？利用容斥思想，减去含1个质数乘积平方因数的数个数，加上含2个质数乘积平方因数的数个数，再减去含三个质数乘积平方因数的数个数……

　　简单来说就是∑⌊n√⌋i=1μ(i)⋅⌊ni2⌋∑i=1⌊n⌋μ(i)⋅⌊ni2⌋，

　　μ函数就是容斥系数，如果n的约数中同个质数的指数大于1，μ(n)值为0，含奇数个质数约数就为-1，含偶数个就为1。

　　μ函数的话可以用线性筛预处理出吧。

　　答案不会超过2*n，神奇啊（我是蒟蒻不会证）。。。

　　时间复杂度O(T*sqrt(n))

#include <cstdio>

#include <iostream>

#define N 50010

using namespace std;

int Q,l,r,o,n,mu[N],prime[N],cnt;

bool flag[N];

void Pre()

{

mu[1]=1;

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

{

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

for (int j=1;j<=cnt;++j)

{

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

flag[i*prime[j]]=1;

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

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

}

}

}

bool check()

{

int tot=0;

for (int i=1;i<N && (long long)i*i<=o;++i)

tot+=o/(i*i)*mu[i];

return tot>=n;

}

int main()

{

cin>>Q;

Pre();

while (Q--)

{

l=0,r=2e9;

cin>>n;

while (l<r)

{

o=((long long)l+r)>>1;

if (check()) r=o;

else l=o+1;

}

cout<<l<<endl;

}

return 0;

}

//转自lzw大神的blog