BZOJ 2440 [中山市选2011]完全平方数

二分+莫比乌斯函数+容斥原理

方便起见,我们描述完全平方数及其倍数为不合法数,其余为合法数。

二分答案x,找小于x的合法数有多少即可。然而这并不好找,我们来找不合法数。一个合数的平方的倍数一定也能写成一个质数的平方的倍数,因此只考虑质数的平方。一个完全平方数 i2 ,它的贡献 xi2 。然而这样算是会算重的,比如 36=2232 。然后考虑容斥。记 22 及其倍数为集合 S1 32 及其倍数为集合 S2 。。。然后我们就是要求他们的交集。容斥系数只与质因数个数有关,这不就直接等于莫比乌斯函数。。。

#include<cstdio>
#include<cmath>
#define N 50000
using namespace std;
namespace ziqian
{
    typedef long long ll;
    bool notprime[N];
    int miu[N], prime[N], pcnt;

    int check(int mid)
    {
        int ans = mid;
        for(int i = 2, ii = sqrt((double)mid); i <= ii; i++)
            ans += mid/(i*i) * miu[i];
        return ans;
    }

    void main()
    {
        miu[1] = 1;
        for(int i = 2; i < N; i++)
        {
            if(!notprime[i]) prime[++pcnt] = i, miu[i] = -1;
            for(int j = 1; j <= pcnt && i * prime[j] < N; j++)
            {
                notprime[i * prime[j]] = 1;
                if(i % prime[j]) miu[i*prime[j]] = -miu[i];
                else break;
            }
        }

        int T;
        scanf("%d",&T);
        for(; T--; )
        {
            ll l = 1, r = 2000000000ll, k;
            scanf("%lld",&k);
            for(; l < r; )
            {
                ll mid = (l+r)>>1;
                if(check(mid) < k) l = mid + 1;
                else r = mid;
            }
            printf("%lld\n",l);
        }
    }
}   
int main()
{
    ziqian::main();
}
相关文章
相关标签/搜索