🐢
[鉄則B29] Power Hard
前問とあまり違いがない繰り返し二乗法問題。
問題を要約する
- a の b 乗を 1000000007 で割った余りで出力せよ
- b の最大は 10**18
実装 (AC)
44 ms
a, b = gets.split.collect(&:to_i) # => [123456789, 123456789012345678]
MOD = 1000000007
acc = 1
x = a
until b.zero?
if b.anybits?(1)
acc = (acc * x).modulo(MOD) # => 643499475, 213046201, 999256206, 322919510, 74655874, 431509073, 321388980, 291295321, 673739962, 385031283, 529603331, 926897054, 969450360, 602796360, 362851968, 538243293, 199603715, 773931420, 134332472, 191050174, 217400649, 139508494, 51916770, 521597215, 495630228, 954083627, 868637264, 835291101, 564930313, 818880493, 3599437
end
b = b >> 1
x = (x * x).modulo(MOD) # => 643499475, 426634628, 534578656, 450345977, 580404050, 898320494, 291546108, 494953740, 25133179, 682224309, 532517453, 764583364, 413442484, 379547454, 829488240, 481942455, 305547329, 605520058, 73741598, 237528843, 861978999, 515987478, 589098959, 65620614, 951594548, 444599065, 215195936, 546751066, 79579274, 806037056, 97277019, 359286635, 186015030, 143689763, 846468940, 369155973, 447643812, 19196477, 726632001, 181305574, 933367506, 158435771, 356651190, 438015610, 260668389, 548219265, 413329705, 839496924, 472176216, 395426017, 825952158, 529478230, 81502542, 305963116, 697135467, 947323104, 90247417
end
p acc # => 3599437
模範解答ではマジックナンバー 60 が出てくる。b の最大が 10**18 で、それを超えない最大が 2**59 のため回数で言えば 60 回
b = 10**18 # => 1000000000000000000
((2**59)...(2**60)).cover?(b) # => true
ということなのだが、b が 0 になった時点で終わればループ回数をハードコーディングする必要がなくなる。
a.pow(b, MOD) を使う
45 ms
a, b = gets.split.collect(&:to_i) # => [123456789, 123456789012345678]
MOD = 1000000007
p a.pow(b, MOD) # => 3599437
Discussion