bzoj2440: [中山市选2011]完全平方数

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

BZOJ 2440

【题意】

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

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

【题解】

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

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

　　然后考虑求出f（n）。

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

　　简单来说就是$\sum_{i= 1}^{\left \lfloor \sqrt{n} \right \rfloor}μ\left ( i \right )\cdot  \left \lfloor \frac{n}{i^{2}} \right \rfloor$，

　　μ函数就是容斥系数，如果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;
}