次方求模

算法

问题

求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