xjoi训练赛 cbh场t1

这题是今天早上补的

现在写一发简单的题解吧

cbh写的好详细的

题意就不写了吧:中文题。。

题解:

首先我们可以发现一个性质

对于每一个素数p

G是对于素数小于等于p构成的集合

x\in{G} 并且 x is not goodnumber

我们可以发现 x*p^{k}一定不是好数

于是我们就有如下的算法

首先先加入1这个数,然后不断地枚举素数,在生成的好数的集合中继续筛选,由上面的结论可知,好数筛选出的数可能是好数,于是不断用类似插入排序的思想维护这个集合就行了

经过不断迭代,我们可以发现,我们枚举的素数的范围到293就已经迭代到稳定了

具体怎么实践出来的,你通过二分范围的值,输出1e18里面的好数的个数就行了

时间复杂度O(NKlg(1e18))

N1e18 内的好数的个数

k=233差不多有50000

发表评论

电子邮件地址不会被公开。 必填项已用*标注