怎么快速把一个数N分为最接近的a^b形式

qianyb · 发表于 2011-3-1 15:09:21

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

×

怎么快速把一个数N分为最接近的a^b形式
例：
8＝2^3
26=5^2
126=5^3

wayne · 发表于 2011-3-1 15:50:14

我来抛一个转头
=============
a^b=N
b* lg a =lg N
所以，我们可以设计这样的算法，对于小于N的所有正整数 i，计算 t =round ( lgN/lg i ) , 计算c =| i^t -N| , 记录下最小的c所对应的i，。。。。。。。
算法复杂度，O(N)

mathe · 发表于 2011-3-1 16:27:21

穷举所有小于N的i,复杂度太大了,不如穷举b,$2<=b<=log_2(N)$,这个复杂度为O(log(N))
也就是我们计算$root{b}{N}$,分别舍入得到两个不同的a的选择.然后对所有的选择a,b,找误差最小的一个.

gxqcn · 发表于 2011-3-1 16:28:02

26=5^2 or 26=3^3 ？

mathe · 发表于 2011-3-1 16:29:30

如果我们另外考虑到如果存在合数$b=b_1*b_2$,那么$(a^{b_1})^{b_2}$不会差于$a^b$,所以我们只需要穷举素数形式的b即可,那么可以穷举更少一点的结果,但是总体复杂度不会降低(除非素数表事先给出)

wayne · 发表于 2011-3-1 16:29:57

4# gxqcn
都算，呵呵

qianyb · 发表于 2011-3-1 17:03:16

4# gxqcn

本来结果是$5^2$,但也可以是$3^3$,最相近的结果也可以

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

[求助] 怎么快速把一个数N分为最接近的a^b形式