🐢
[鉄則A29] Power (繰り返し二乗法)
pow の内部実装(繰り返し二乗法)が学べる問題。
問題を要約する
- a の b 乗を 1000000007 で割った余りで出力せよ
考え方
余りで丸めるのはいったん置いといて3の10乗で考える。答えは、
3**10 # => 59049
となるのだが、3 を 10 回掛けてはいけない。
3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 * 3 # => 59049
正しくは二進数の桁の値を指数として基数 3 を累乗する。
3**1 # => 3
3**2 # => 9
3**4 # => 81
3**8 # => 6561
| 8乗 | 4乗 | 2乗 | 1乗 |
|---|---|---|---|
| 6561 | 81 | 9 | 3 |
次に指数は 10 なので対応する 8 乗と 2 乗の位置の値を掛ける。
6561 * 9 # => 59049
これだけ。あとはこの計算の途中で毎回余りを求めるようにする。
単純な実装 (TLE)
a, b = gets.split.collect(&:to_i) # => [3, 10]
MOD = 1000000007
acc = 1
b.times { acc = (acc * a).modulo(MOD) }
p acc # => 59049
a を b 回掛ける方法では TLE になる。指数ことループ回数が多くなると破綻する。
解説の模範解答 (AC)
135 ms
a, b = gets.split.collect(&:to_i) # => [97, 998244353]
MOD = 1000000007
acc = 1
x = a
30.times do |i|
if b.anybits?(1 << i)
acc = (acc * x).modulo(MOD) # => 97, 477410631, 400447012, 832709201, 594079130, 593767246, 934801994
end
x = (x * x).modulo(MOD) # => 9409, 88529281, 539514930, 655370401, 500328288, 20712186, 645895638, 267158840, 290528685, 216980813, 880576265, 53448354, 525312234, 258400169, 871834039, 238391419, 255020285, 306233810, 730662085, 719477679, 955690159, 616039570, 149251657, 961313257, 615085852, 682251690, 249584545, 666809917, 297098655, 184935755
end
p acc # => 934801994
急に出てきたマジックナンバー 30 とは何だろうか？ これは b の最大が 10**9 で、それを超えない最大が 2**29 のため回数で言えば 30 回ということらしい。
10**9 # => 1000000000
(2**29)..(2**30) # => 536870912..1073741824
リファクタリング後 (AC)
44 ms
a, b = gets.split.collect(&:to_i) # => [97, 998244353]
MOD = 1000000007
acc = 1
x = a
until b.zero?
if b.anybits?(1)
acc = (acc * x).modulo(MOD) # => 97, 477410631, 400447012, 832709201, 594079130, 593767246, 934801994
end
b = b >> 1
x = (x * x).modulo(MOD) # => 9409, 88529281, 539514930, 655370401, 500328288, 20712186, 645895638, 267158840, 290528685, 216980813, 880576265, 53448354, 525312234, 258400169, 871834039, 238391419, 255020285, 306233810, 730662085, 719477679, 955690159, 616039570, 149251657, 961313257, 615085852, 682251690, 249584545, 666809917, 297098655, 184935755
end
p acc # => 934801994
マジックナンバー 30 を消したもの。b を右シフトして 0 になったら早めに終わるようにすればすっきりして計算時間も短かくなる。
Ruby の Integer#pow 実装
似たようなコードになっているのがわかる。
a.pow(b, MOD) を使う
Ruby の実装を見ていて気づいたが pow には第二引数があって、
45 ms
a, b = gets.split.collect(&:to_i) # => [97, 998244353]
MOD = 1000000007
p a.pow(b, MOD) # => 934801994
** や pow をそのまま使うと、
a**b # => Infinity
a.pow(b) # => Infinity
となってしまうが第二引数に modulo の引数を渡せば、
a.pow(b, MOD) # => 934801994
内部で丸めてくれる。
Discussion