# Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

# The beginning of things

In Ruby, there is a dedicated method Integer # pow.

I tried it immediately. 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)
``````
Code length(Byte) 50 183
Execution time(ms) 68 62
memory(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)
``````
Code length(Byte) 305 438
Execution time(ms) 101 100
memory(KB) 22676 22488

# Acing Programming Contest 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
``````
All of them were equal or better. The era of `ruby` has arrived.