Ruby で 繰返し二乗法 を解くなら Integer#pow がお薦め

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

事の始まり

Ruby と Perl と Java と Python で解く AtCoder ATC 002 B 繰返し二乗法 でコメントをいただきました。

Ruby だと専用メソッド Integer#pow がありますね。

早速試しました。

AtCoder Typical Contest 002 B - n^p mod m

pow.rb

n, m, p = gets.split.map(&:to_i)
puts n.pow(p, m)

zisaku.rb

n, m, p = gets.split.map(&:to_i)
def mpow(n, p, mod)
  r = 1
  while p > 0
    r = r * n % mod if p % 2 == 1
    n = n * n % mod
    p >>= 1
  end
  r
end
puts mpow(n, p, m)

	Integer#pow	自作mpow
コード長 (Byte)	50	183
実行時間 (ms)	68	62
メモリ (KB)	14356	14356

AtCoder Regular Contest 066 C - Lining Up

pow.rb

n = gets.to_i
a = gets.split.map(&:to_i)
h = Hash.new(0)
a.each do |x|
  h[x] += 1
end
f = true
h.each do |k, v|
  if n.odd? && k == 0
    if v != 1
      f = false
      break
    end
  elsif v != 2
    f = false
    break
  end
end
MOD = 1_000_000_007
puts (f ? 2.pow(n / 2, MOD) : 0)

	Integer#pow	自作mpow
コード長 (Byte)	305	438
実行時間 (ms)	101	100
メモリ (KB)	22676	22488

エイシング プログラミング コンテスト 2020

pow.rb

n = gets.to_i
x = gets.chomp
xs = x.to_i(2)
xc = x.count('1')
def mpow(n, p, mod)
  return 0 if mod.zero?
  n.pow(p, mod)
end
def popcount(u)
  return 0 if u.zero?
  a = u % u.to_s(2).count('1')
  1 + popcount(a)
end
xsp = mpow(xs, 1, xc + 1)
xsm = mpow(xs, 1, xc - 1)
n.times do |i|
  if x[i] == '0'
    y = xsp + mpow(2, n - i - 1, xc + 1)
    y = mpow(y, 1, xc + 1)
  elsif xc == 1
    puts '0'
    next
  else
    y = xsm - mpow(2, n - i - 1, xc - 1)
    y = mpow(y, 1, xc - 1)
  end
  puts popcount(y) + 1
end

	Integer#pow	自作mpow
コード長 (Byte)	541	629
実行時間 (ms)	421	625
メモリ (KB)	14704	15392

いずれも同等以上の成績でした。
rubyの時代が来ましたね。

まとめ

• Integer#pow を使おう
• Ruby の時代が来た

参照したサイト
instance method Integer#**
Ruby と Perl と Java と Python で解く AtCoder ATC 002 B 繰返し二乗法
Ruby と Python で解く AtCoder ARC 059 C 最小二乗法
Ruby と Python で解く AtCoder AISING2020 D 繰返し二乗法