Vijos P1889 天真的因数分解

2023-10-09 05:38

本文主要是介绍Vijos P1889 天真的因数分解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

小岛: 什么叫做因数分解呢?
doc : 就是将给定的正整数n, 分解为若干个素数连乘的形式.
小岛: 那比如说 n=12 呢?
doc : 那么就是 12 = 2 X 2 X 3 呀.
小岛: 呜呜, 好难, 居然素数会重复出现, 如果分解后每一个素数都只出现一次, 我就会.

wish: 这样来说, 小岛可以正确分解的数字不多呀.
doc : 是呀是呀.
wish: 现在问题来了, 对于给定的k, 第 k 个小岛无法正确分解的数字是多少?

格式

输入格式

输入只有一行, 只有一个整数 k.

输出格式

输出只有一行, 只有一个整数, 表示小岛无法正确分解出来的第k个数字.

样例1

样例输入1[复制]

10

样例输出1[复制]

27

限制

对于30%的数据, k <= 2,000,000
对于100%的数据, 1 <= k <= 10,000,000,000

莫比乌斯反演。。。

二分+判定

小于x的可以正确分解的数字个数是 Σmu[i]*(x/i^2)

然后可以稍微把mu函数改改即可。。。

二分的上界可以测一下。。。

#include<iostream>
#include<climits>
#include<cstdio>
#include<cmath>
using namespace std;
long long ans,k,T,n=160000;
int tot,mu[200005],p[200005],ma[200005];
inline void getmu()
{for(int i=2;i<=n;++i){if(!ma[i])p[++tot]=i,mu[i]=1;for(int j=1;j<=tot&&p[j]*i<=n;++j){ma[i*p[j]]=1;if(i%p[j]==0){mu[i*p[j]]=0;break;}else mu[i*p[j]]=-mu[i];}}
}
long long te(long long x)
{long long sum=0,t=sqrt(x);for(long long i=1;i<=t;++i)sum+=x/(i*i)*mu[i];return sum;
}
int main()
{getmu();scanf("%lld",&k);long long l=k,r=25505460948LL;while(l<=r){long long mid=l+r>>1;if(te(mid)>=k)ans=mid,r=mid-1;else l=mid+1;}printf("%lld\n",ans);
}

这篇关于Vijos P1889 天真的因数分解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/170713

相关文章

为什么现在很多人愿意选择做债务重组?债重组真的就这么好吗?

债务重组,起初作为面向优质企业客户的定制化大额融资策略,以其高效周期著称,一个月便显成效。然而,随着时代的车轮滚滚向前,它已悄然转变为负债累累、深陷网贷泥潭者的救赎之道。在此路径下,个人可先借助专业机构暂代月供,经一段时间养护征信之后,转向银行获取低成本贷款,用以替换高昂网贷,实现利息减负与成本优化的双重目标。 尽管债务重组的代价不菲,远超传统贷款成本,但其吸引力依旧强劲,背后逻辑深刻。其一

写给大数据开发:你真的“慢“了吗?揭秘技术与职场的平衡艺术

你是否曾经在深夜里,面对着一个棘手的数据处理问题,感到无比沮丧?或者在一次重要的项目汇报中,突然语塞,无法清晰地表达你的技术方案?作为一名大数据开发者,这些场景可能再熟悉不过。但别担心,因为你并不孤单。让我们一起探讨如何在这个瞬息万变的行业中,既磨练技术利刃,又培养职场软实力。 目录 技术与时间的赛跑1. 长远视角的重要性2. 复利效应在技能学习中的应用 跨界思维:数据结构教我们的职场智

【数据结构】你真的学会了二叉树了吗,来做一做二叉树的算法题及选择题

文章目录 1. 二叉树算法题1.1 单值二叉树1.2 相同的树1.3 另一棵树的子树1.4 二叉树的遍历1.5 二叉树的构建及遍历 2. 二叉树选择题3. 结语 1. 二叉树算法题 1.1 单值二叉树 https://leetcode.cn/problems/univalued-binary-tree/description/ 1.2 相同的树 https://leet

4所适合职场人读的海外在线硕士院校,真的靠谱!

不用参加硕士研究生统考、不用出国、线上上网课就能读全球排名前列院校的硕士研究生。 这让很多想自我提升,但是因为工作繁忙没时间准备国内硕士联考、也没时间出国留学,以及一些毕业多年,应试能力下降、多次联考不过的职场人士有些蠢蠢欲动。 但是这个领域实在过于陌生,很多同学不了解、也没有靠谱的了解渠道,看到各种世界排名靠前院校的海外硕士的招生信息,心动过后也只能继续观望。 不出国门、免考试,就能获取海

软考证书补贴动不动就好几万,真的能领到吗?

取得软考证书在许多地区都有补贴政策,从几千至二十几万元不等。有些考生会好奇这些补贴是真的能领到吗,为此,小希搜集了一些例子证明是可以领到的,供大家参考。 1、奖励名单里的软考证书         在一些地区公示的奖励名单里,奖励人员的职称类别是软考资格名称,职称取得时间是软考考试时间,证明确实是通过软考考试取得职称后申请的补贴。 ✅湖南省常德市         2024年6

护眼灯真的可以保护眼睛吗?曝光劣质护眼台灯常见的三个特征

护眼灯真的可以保护眼睛吗?随着时代的发展,我们注意到越来越多的孩子开始佩戴眼镜。这一趋势引起了许多细心家长的关注,他们认识到这不仅是个别情况,而是现代生活方式和环境对孩子视力健康的挑战。自然而然地,“儿童是否应该使用护眼灯”成为了家长们关心的问题。作为专业测评师,我将针对这一问题提供多维度的科普知识。如果你正在考虑购买护眼灯,不妨花一点时间继续阅读下文。 一、护眼灯真的可以保护眼睛吗?

宠物空气净化器真的有用吗?哪款能真的起到吸毛除臭效果

现在养猫养狗已经成为了一个浪潮,甚至有人发了一张对比图:在店门口,偏年老一代的就是抱着小孩,但年轻一辈的就是抱着宠物。虽然说不管是养猫养狗还是养小孩都是自己的选择,但是显而易见的就是现在大街上宠物出现的频率明显变多,对于大部分独居青年而言,养宠物反而是一个精神寄托,甚至成为精神支撑,支撑着这些年轻人在城市里打拼。 对于我而言,之前养猫就是觉得一个人太孤独,回到家后发现家里并没有什么能和我

宠物空气净化器真的有用吗?去浮毛好用的宠物空气净化器推荐

不知不觉我已经养宠五年了,一人两猫作伴的日子充满着幸福,可猫毛的存在偶尔也会让小家出现裂缝。每当换毛季,我的鼻子就率先作出反应,瘙痒加上止不住喷嚏都在反映着不佳的空气质量。这都是因为猫咪疯狂掉毛,浮毛上附着的细菌随着呼吸进入到人体,引起各种反应。 朋友在看到后,推荐我买台宠物空气净化器来改善家中的环境。相信很多人和我一样,对宠物空气净化器了解不是很多,更别提知道它的功能了。为了可以减轻家中猫毛打

真的很充实。。

真的很充实。。 本随笔文章,由个人博客(鸟不拉屎)转移至博客园 写于:2017 年 12 月 22 日 原地址:https://niaobulashi.com/archives/enrich.html --- 阴阳师开新服了,我到新服务,果断非洲酋长,要哭了 最近在完成各种需求 完全是一个人在搞,也慢慢的在完全接手这个项目,但是还有不懂的地方 一边学习一边开发的过程。 晚上下班了就学习

最近真的很忙

最近真的很忙 本随笔文章,由个人博客(鸟不拉屎)转移至博客园写于:发布时间:2017 年 11 月 28 日 原地址:https://niaobulashi.com/archives/toobusy.html--- 最近是真的很忙,上个周四上线(平台新增网易支付渠道)涉及到上线的系统有(前端、管理端、支付、账户、清算、营销系统、前端通讯)真的很多需要变更单单新增一个支付渠道,就需要变更