7K12 blog

猫でも分かる何か

AOJ NTL_1_B Power

f:id:tkr987:20200802001342p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4728976

  • 繰り返し二乗法を使うと累乗は O(\log N)

f:id:tkr987:20200802003418p:plain

mのn乗をするのにn回だけ掛け算するのは制約からTLEする。

二乗した値を二乗することで木構造と同じ理由でO(\log N)で計算できるようになる。