注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【算法】【十进制快速幂】  

2014-04-04 11:01:37|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      额,貌似上午还木有写出什么东西来...所以就来写(Chao)一写(Chao)十进制快速幂。
     贴一下缘由应该没什么错吧...(如果有错非常抱歉= =咱马上删)
    【算法】【十进制快速幂】 - z55250825 - z55250825
    再次orz科普十进制快速幂的 xtikabb 君(这应该是非常简单的凯撒了吧...)
    首先这不是二进制快速幂咩...咱一开始就体现出了蒟蒻的智商= =。
    假设咱们需要求 m^n,咱们有一种方法是 二进制快速幂,这个的复杂度是O(logn)的。但是咱们还可以做的更好实际上....咱们把 n拆成10进制表达式,比如 :
234=2*10^2+3*10+4,
139476=1*10^5+3*10^4+9*10^3+4*10^2+7*10^1+6
咱们设拆成的形式是
n=a0+a1*10^1+a2*10^2...+ai*10^i+...+ad*10^d,d为n的最高位,其实就是d=【logn】(log以10为底数)
然后这个表示出来了咱们有:
m^n=m^(a0+a1*10^1+a2*10^2+...+ai*10^i...+ad*10^d)(ak∈【0,9】,k∈【1,d】)
看出一点来了吧...
咱们可以化成 m^n=m^a9*(m^a1)^10*(m^a2)^100....
继续化简,咱们有 m^n=(((m^ad)^10*ad-1)^10*m^ad-2).....
这个实际上就很好做了,由于 0<=ai<=9,只需要预处理下m^0~m^9即可很快计算出m^ai,然后这个就是O(logn)的,(log以10为底),只不过需要加个10的常数,不过这个的效率在n达到10^100就可以体现了=w=。
即算法流程就是初始化ans=1,从n的最高位开始,每一次提取一位w,用ans乘以m^w然后再做10次的幂,重复到n的所有位都取完了即可。即这个算法的复杂度只与n的位数有关,预处理10个数复杂度也不是很高。
然后取最高位只需要一开始分解每个位存在一个数组里面即可,这里假设是a[],然后预处理的m^0~9在mm[]里,下面就是伪代码:

function quickmod(n:int64):int64;
begin
    len=0;tmp=n
    while tmp!=0 do
        len=len+1
       a[len]=tmp mod 10;
       tmp=tmp div 10;
    ans=1
    for i=len downto 1 do
      ans=ans*mm[a[i]]
      ans=ans^10
    return ans
end

    
再举个例子吧...
比如 2^154,咱们就有 2^154=((2^1)^10*2^5)^10*2^4 咱们拆开来自然可以检验出这个是不是正确的了。
再比如 2^1512526,咱们就有
2^1512526=((((((2^1)^10*2^5)^10*2^1)^10*2^2)^10*2^5)^10*2^2)^10*2^6
为什么要用十进制快速幂?显然可以发现它的表示实际上比二进制更自然吧...每次只需要取最高位就可以了而不需要考虑什么二进制的原理,显然是十分方便的。而且复杂度比二进制的复杂度更小,还是非常不错了。
  评论这张
 
阅读(189)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017