jtahstu的博客

1373758426   Git仓库   GitBook  

最新碎语:以后没事写写小的知识点吧

您的位置:jtahstu的博客 >算法> 次方求模 - Ruby

次方求模 - Ruby

MarkDown版 https://www.zybuluo.com/jtahstu/note/779922


次方求模

算法


问题

求a的b次方对c取余的值

解题思路

由公式:a^p mod m = (a mod m)^p mod m

应用

典型的就是南阳OJ102题,次方求模

代码

# author: jtusta
# contact: root@jtahstu.com
# site: http://www.jtahstu.com
# software: RubyMine
# time: 2017/6/9 03:54
class PowMod
  # 循环写法
  def powMod(a,p,m)
    res = 1
    while p>0
      if p%2==1
        res = (res*a)%m
      end
      a = (a*a)%m
      p >>= 1
    end
    res
  end

  # 递归写法
  def powMod_2(a,p,m)
    res = 1
    if p==0
      return 1%m
    end
    if p==1
      return a%m
    end
    res = self.powMod_2(a,p/2,m)
    res = res*res%m
    if p%2==1
      res = res*a%m
    end
    res
  end
end


test = PowMod.new
p test.powMod(11,12345,12345)
p test.powMod_2(11,12345,12345)
运行结果


/usr/bin/ruby -e $stdout.sync=true;$stderr.sync=true;load($0=ARGV.shift) /Users/jtusta/Documents/Code/Ruby/algorithm/pow_mod.rb
10481
10481

Process finished with exit code 0


---

本文章采用 知识共享署名2.5中国大陆许可协议 进行许可,欢迎转载,演绎或用于商业目的。

---

二维码加载中...

扫一扫移动端访问O(∩_∩)O

发表评论

50 + 67 =
路人甲 表情
看不清楚?点图切换 Ctrl+Enter快速提交
正在加载中……