No.16

$x^{2^n}$ をあらかじめ計算しておく. $a_k$ を $2^m$ の和に分解 (2進数に変換して立っているビットを取得) して, 計算しておいた $x^{2^n}$ を足していく.