uva11752——快速幂+set妙用
发布日期:2021-05-18 06:05:31 浏览次数:19 分类:精选文章

本文共 612 字,大约阅读时间需要 2 分钟。

首先,我需要找到1到2^64−1之间所有超级数。超级数的定义是至少可以表示为两个不同的正整数的幂次方。例如,64可以表示为8²和4³,因此它是一个超级数。

为了高效地找出所有超级数,我需要寻找那些可以表示为a^b的数,其中b≥2。为了确保这些数是在1到2^64−1之间,我需要确定最小的指数范围。例如,当a=2时,最大的指数b满足2^b ≤2^64−1。

接下来,我需要考虑如何计算这些超级数。直接暴力分解质因数可能效率低下,因此我采用了一种更高效的方法:找到所有可能的a^b值,并确保这些值在范围内。

首先,我确定最小的指数b。对于b=2,所有的完全平方数都是超级数;同样地,b=3的完全立方数也是超级数。继续这样,直到最大的可能指数b。

为了找到最大的指数b,我需要计算满足a^b ≤2^64−1的最大b。考虑到2^64已经超过了2^64−1,最大的指数b是63。

接下来,我遍历每一个可能的指数b,从2到63,并为每个b找到所有满足条件的a的幂次方。例如,当b=2时,所有的完全平方数都是超级数。

在遍历时,我使用快速幂算法来计算a^b,以确保计算的效率和准确性。然后,将所有计算得到的值存入一个集合中,以避免重复。

最后,我将集合中的所有数排序,并按升序输出,确保符合题目的要求。

通过这种方法,我能够准确地找出所有超级数,并按照要求输出。

$$ \boxed{1, 16, 64, 81, 256, 512} $$

上一篇:大一暑假集训总结(2019)
下一篇:uva11827——最大公约数+输入处理(stringstream)

发表评论

最新留言

网站不错 人气很旺了 加油
[***.192.178.218]2025年04月28日 08时09分59秒