BZOJ2440(全然平方数)二分+莫比乌斯容斥

全栈程序员站长

发布于 2022-07-12 18:07:43

1410

发布于 2022-07-12 18:07:43

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

题意：全然平方数是指含有平方数因子的数。求第ki个非全然平方数。

解法：比較明显的二分，getsum(int middle)求1-middle有多少个非全然平方数，然后二分。求1-middle的非全然平方数个数能够用总数减掉全然平方数个数。计算全然平方数的个数用容斥：

首先加上n/(2*2)+n/(3*3)+n/(5*5)+n/(7*7)…+…然后减掉出现两次的，然后加上三次的…奇加偶减。这就是mou的原型，用mou数组计算非常easy；

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
#define zero(_) (abs(_)<=eps)
const double pi=acos(-1.0);
typedef unsigned long long LL;
const int Max=100010;
const LL INF=2e16+7;

LL mou[Max];
void init()
{
    for(LL i=2; i<Max; i++)
    {
        if(!mou[i])
        {
            mou[i]=i;
            for(LL j=i*i; j<Max; j+=i)
                mou[j]=i;
        }
    }
    mou[1]=1;
    for(int i=2; i<Max; i++)
    {
        if(i/mou[i]%mou[i]==0) mou[i]=0;
        else mou[i]=-mou[i/mou[i]];
    }
}
int k;
LL getnum(LL middle)
{
    LL ans=0;
    for(LL i=1; i*i<=middle; i++)
    {
        ans+=mou[i]*(middle/(i*i));
    }
    return ans;
}
int main()
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        scanf("%d",&k);
        LL left=1,right=INF;
        while(left<=right)
        {
            int middle=(left+right)/2;
            if(getnum(middle)<k)
                left=middle+1;
            else
                right=middle-1;
        }
        cout<<left<<'\n';
    }
    return 0;
}

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/118488.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年12月，如有侵权请联系 cloudcommunity@tencent.com 删除

java