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

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

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

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


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

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

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

代码:

/******************************************************
* @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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118488.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • cubieboard服务器系统,CubieBoard_搭建自己的系统.pdf

    cubieboard服务器系统,CubieBoard_搭建自己的系统.pdfCubieBoard_搭建自己的系统构建自己的CubieBoardDebianLinuxsoloforce汇编整理2013年10月10日1soloforce摘要本文在x86-64UbuntuLinux上为CubieBoard(包括A10单核和A20双核系统)构建一个基于ARMHF的DebianLinux,包括SPL、U-BOOT、内核(Kernel)、根系统…

  • TK-MyBatis 分页查询「建议收藏」

    TK-MyBatis 分页查询「建议收藏」记tkMybatis查询出一个 List集合该集合已经做好了一层分页Page封装即查询出的list使用类型判断instanceofPage为true但是,中途不明白这是一个带分页的集合,把查询出的结果集又做了一层封装需要返回的对象类型为GoodsCategoryDTO,代码如下:   //商品集合        List&lt;GoodsCategory…

  • H5音乐标签实现网页自动播放和隐藏

    H5音乐标签实现网页自动播放和隐藏网页播放音乐如果不能自动播放,用iframe放在body最下面。即可运行。<iframesrc=”no.mp3″allow=”autoplay”hidden/>

  • Vue(renren-fast_vue_master)项目目录结构[通俗易懂]

    Vue(renren-fast_vue_master)项目目录结构[通俗易懂]打算做一个请假管理OA项目Demo,后端采用renren-fast框架,后台管理系统采用renren-fast_vue_master项目,打算利用renren-fast-vue-master改造成一个简单的请假管理系统,包含注册、登陆、请假流程查看等等简单的展示即可,由于之前没做过Vue,现简单地介绍下项目目录结构:├──build/#Webpack配…

    2022年10月28日
  • 微信公众号代理运营公司_多平台推广

    微信公众号代理运营公司_多平台推广最近公司项目需要切到微信服务号,但是公司内网环境需要开防火墙策略才能访问微信的开放API,实际上就是通过代理去访问。这里记录一下我通过代理去调用微信API遇到的坑及解决办法。

  • navicat premium 15激活码最新[在线序列号]

    navicat premium 15激活码最新[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号