繰り返し自乗法 - sataniC++概要 の値を効率的に解きます。 使える状況 「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。 説明 の値を求めたいとき、愚直な方法として次のような手法を考えることが出来ます。 using ll = long long int; ll PowMod(ll N, ll P, ll M){ ll ans = 1; for(ll i=0; i<P; ++i){ ans *= N; ans %= M; } return ans; } しかし、上記のような方法だと回ループしてしまうため、などの場合では非常に時間がかかってしまいます。 そこで使うのが、繰り返し自乗法です。 繰り返し自乗法は、 「を一回一回掛けてmodを取るのでは時間がかかるので、まとめて掛けてしまおう！
