SRM660 div2 1000
考え方
i^(2^k-1)を考える。
k=400まであるので、愚直な方法では桁あふれしてしまう。
2^k-1というのは、ビットレベルで考えると2^kはk+1ビット目だけ立っていて、2^k-1は1ビット目〜kビット目まですべて立っている。なので、1+2+4+8+16+32+...とk個分足し合わせたものと一致する。
なので、i^(2^k-1)の計算は、i^1 * i^2 * i^4 * ...とk個分掛け合わせたものになる。i^4は(i^2)*(i^2)で求められるように、一つ前の結果を2乗すれば求めていける。
これで、一つあたりの累乗計算はO(k)で行える。
しかし、これだけだとiが10^6あるため、O(n*k)=O(4*10^8)でTLEになってしまう。
そこで、「素因数関係の列挙」でまとめてた「整数xの重複を含めた素因数の総数の列挙」と同様の方法を使う。
http://d.hatena.ne.jp/phyllo_algo/20150525/1432566924
整数iの最大素因数をO(nloglogn)程度で列挙しておき、iが小さいほうから
・素数なら累乗計算で求める
・素数でないなら、「(iの最大素因数)の累乗結果」と「i/(iの最大素因数)の累乗結果」を掛け合わせて求める
方法で計算できる。
累乗計算は素数の数分だけで、それ以外はO(1)で求められるので、十分間に合う。
(別に最大素因数じゃなくてもいい)
ちなみに、iを素因数分解し、i=j*k*...ならば、jの累乗計算結果 * kの累乗計算結果 * ...と累乗計算の結果をメモりながら計算する方法でもギリギリ間に合ってる。(1.99秒台とかでるけど・・・)
