繰り返し2乗法

Atcoder典型90問 069★3[繰り返し2乗法]

■要約 N=1以外の時は,総数がK*(K-1)*(K-2)^(N-2)になることはすぐに分かったが,累乗の計算量はO(N)なのでどうしようかと考えていた.調べたら,繰り返し2乗法というものがあり,計算量をO(logN)に減らせる. 説明は他の方々がとてもわかり易いものを記載しているので割愛する. pythonだとわざわざ実装しなくても pow(x,y,n)でx^yをnで割ったあまりをO(logN)で計算してくれるらしい.鬼便利 N, K = map(int, inp

Python で繰り返し2乗法を書いてみた

繰り返し2乗法とは指数を2の累乗の積に分解して計算を効率化するテクニック。計算量が Olog(N) になる。 ただし Python の場合は組み込みの関数として pow が実装されているが勉強のため書いてみた。 // 3 の 50 乗の計算x = 3n = 50def pow(x, n): ans = 1 // n が 0 になるまで計算を続ける while n: if n % 2: ans *= x x