[关闭]
@jtahstu 2017-06-08T20:25:50.000000Z 字数 640 阅读 204

次方求模

算法


问题

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

解题思路

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

应用

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

代码

  1. # author: jtusta
  2. # contact: root@jtahstu.com
  3. # site: http://www.jtahstu.com
  4. # software: RubyMine
  5. # time: 2017/6/9 03:54
  6. class PowMod
  7. # 循环写法
  8. def powMod(a,p,m)
  9. res = 1
  10. while p>0
  11. if p%2==1
  12. res = (res*a)%m
  13. end
  14. a = (a*a)%m
  15. p >>= 1
  16. end
  17. res
  18. end
  19. # 递归写法
  20. def powMod_2(a,p,m)
  21. res = 1
  22. if p==0
  23. return 1%m
  24. end
  25. if p==1
  26. return a%m
  27. end
  28. res = self.powMod_2(a,p/2,m)
  29. res = res*res%m
  30. if p%2==1
  31. res = res*a%m
  32. end
  33. res
  34. end
  35. end
  36. test = PowMod.new
  37. p test.powMod(11,12345,12345)
  38. p test.powMod_2(11,12345,12345)

运行结果

  1. /usr/bin/ruby -e $stdout.sync=true;$stderr.sync=true;load($0=ARGV.shift) /Users/jtusta/Documents/Code/Ruby/algorithm/pow_mod.rb
  2. 10481
  3. 10481
  4. Process finished with exit code 0
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注