末世苍雪

root@jtahstu.com   Github  

最新碎语:这个M1 MBP, PHP多版本环境装的我极度崩溃, 历时4个小时终于搞定了. 1. brew转不了7.x的环境, 默认只能装8.1, 恶心. 2. Nginx装上了, 但是请求转发不到php-fpm上, 试了各种配置都不行, 删掉Nginx转战Apache, 吐了. 3. 系统自带httpd, brew能装上httpd但搞死启动不了httpd, 只能手动启动和关闭httpd, 无语. 4. 以上问题都解决后, 加上自己写的启动和关闭脚本, 目前能正常跑起来PHP文件了, 开心! 为啥目前没有开源好用的M1 MNMP环境哇, o(≧口≦)o

您的位置:末世苍雪 >算法> 次方求模 - 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: https://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

发表评论

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