c++ - 大きな N に対して 2^n を計算する

Question

mod操作で最大10 ^ 9のNの大きな値に対して2 ^ Nを計算したい。反復アプローチを使用しましたが、入力 10^8 に多くの時間がかかりました。

for(long i=1;i<=n;i++){ res=(res*2)%1000000007 }

n=10^8以上は計算に時間がかかります。

Answer 1

2 倍するだけでなく、2 乗することで速度を上げることができます。たとえば、2*2 => 4、4*4 => 16 のように 2^4 に到達できます。

2 から始めます。N が偶数の場合は、2 乗して N を半分にします。N が奇数の場合は、2 を掛けて N を減らします。モジュラスを適用します。

二乗がオーバーフローしないように注意する必要があるかもしれません。