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)
blank

相关推荐

  • 2. Pycharm的介绍与使用[通俗易懂]

    2. Pycharm的介绍与使用[通俗易懂]使用Python原生IDLEIDLE是Python软件包自带的一个集成开发环境,点击开始–&gt;Python安装包–&gt;IDLE。启动IDLE时,会显示&gt;&gt;&gt;,可以在&gt;&gt;&gt;后面输入代码。在PythonShell输入代码回车后会立即执行,并直接在下面显示执行的结果。如下图所示:在原生IDLE模式下编写的代码只停留于内存当中,当关闭原生IDL…

  • django 验证码_rhino5授权验证失败

    django 验证码_rhino5授权验证失败验证和授权概述Django有一个内置的授权系统。他用来处理用户、分组、权限以及基于cookie的会话系统。Django的授权系统包括验证和授权两个部分。验证是验证这个用户是否是他声称的人(比如用户名

  • memcached

    memcached

  • nginx配置负载均衡,tomcat宕机响应缓慢,自动切换的问题

    nginx配置负载均衡,tomcat宕机响应缓慢,自动切换的问题用了nginx负载均衡后,在两台tomcat正常运行的情况下,访问http://localhost速度非常迅速,通过测试程序也可以看出是得到的负载均衡的效果,但是我们试验性的把其中一台tomcat(serverlocalhost:8080)关闭后,再查看http://localhost,发现反应呈现了一半反映时间快,一半反映时间非常非常慢的情况,但是最后都能得到正确结果。解决办法:问题解决,主要是proxy_connect_timeout这个参数,…

  • OpenStack开发_软件架构与应用开发实践报告

    OpenStack开发_软件架构与应用开发实践报告一起研究系列:OpenStack架构分析与实践

  • c++使用了未定义类型_c++如何新建

    c++使用了未定义类型_c++如何新建一、定义HANDLECreateMutex(LPSECURITY_ATTRIBUTESlpMutexAttributes,//指向安全属性的指针BOOLbInitialOwner,//初始化互斥对象的所有者LPCTSTRlpName//指向互斥对象名的指针);第一个参数是一个指向SECURITY_ATTRIBUTES结构体的指针,一般的情况下,可以是nullptr。第二个参数类型为BOOL,表示互斥锁创建出来后是否被当前线程持有。第三个参数类型为字符串(con

发表回复

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

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