如何快速判定一整数是否为 perfect power？

gxqcn · 发表于 2009-2-18 22:07:03

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

给定一整数n，判定它是否可以表示成 $n=b^r\quad(b,r in Z, r>1)$ 形式？
若可以，则返回 r 可取到的最大值（当 $n=0,+-1$ 时，规定返回 -1，代表无穷大）；否则返回 1

n 可以为一个普通的 32bit/64bit 的整数，
也可以是一个超大整数，
正负不限。

请大家讨论快速算法或提供参考资料，谢谢！

无心人 · 发表于 2009-2-19 08:06:00

应该是利用剩余吧

判定是否是平方剩余
立方剩余
五次剩余

...

13393857589828341511855313113250022632017560146319170093046879854629388139061701
53116497973519619822659493341146941433531483931607115392554498072196837321850491
82097185302887317763432563279639273474427276913080937294774265842484594489569299
3259632864321399559710817770957553728956578048354650708508672

请判定上述数字的b, r是多少？
利用算法
而不是手算

mathe · 发表于 2009-2-19 08:07:18

通常指数不会很大,所以不如直接穷举可能的指数

gxqcn · 发表于 2009-2-19 08:13:43

b=2, r=997

因为我在 HugeCalc 中将那个数转成 16 进制输出，立即就得到结果了。

gxqcn · 发表于 2009-2-19 08:16:41

原帖由 mathe 于 2009-2-19 08:07 发表
通常指数不会很大,所以不如直接穷举可能的指数

确实。

但希望得到一个比较好的策略，使试探的次数尽可能的少。
估计需要事先造好一个小素数表。

mathe · 发表于 2009-2-19 08:18:20

这也是一种方法.想这个例子,由于给出的数字是偶数,我们可以先找出其中素因子2的次数t,然后就知道r是t的约数了,可以降低一点复杂度

无心人 · 发表于 2009-2-19 09:26:21

拜托啊
不要假定是偶数

别的数字太大，有点不合适贴
如果你再取巧
贴另外一个了

呵呵

无心人 · 发表于 2009-2-19 09:29:16

来这个

power.txt (192.25 KB, 下载次数: 3)

gxqcn · 发表于 2009-2-19 09:34:36

6# mathe 的意思是：
如果该数存在小因子p1、p2、…，则得到它们对应的最大指数r1、r2、…
则返回值 r|GCD(r1, r2, ...)，这样可以大幅减少试探的次数。

无心人 · 发表于 2009-2-19 09:36:13

这是个笨方法

记得分解F9的论文上有排除素数的幂的算法

谁能搜到这个算法

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 如何快速判定一整数是否为 perfect power？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复 2# 无心人的帖子

[讨论] 如何快速判定一整数是否为 perfect power？

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复 2# 无心人 的帖子

回复 2# 无心人的帖子