Gọi $S_k$ là ${\displaystyle \sum _{i=1}^n{i}^k}$.

Ta có: $(n+1{)}^{k+1}={\displaystyle \sum _{i=0}^{k+1}{C}_{k+1}^i\ast n^i}$. (Nhị thức Newton)
$⟺(n+1{)}^{k+1}-n^{k+1}={\displaystyle \sum _{i=0}^k{C}_{k+1}^i\ast n^i}$.

Ta lại có: ${\displaystyle \sum _{i=1}^n[(i+1{)}^{k+1}-i^{k+1}]=(n+1{)}^{k+1}-1={\displaystyle \sum _{i=0}^k{C}_{k+1}^i\ast S_i}}$.
$⟺(k+1)\ast S_k=(n+1{)}^{k+1}-1-({\displaystyle \sum _{i=0}^{k-1}{C}_k^i\ast S_i)}$.

Sử dụng công thức trên, ta có thể dễ dàng tính được kết quả trong độ phức tạp $k^2$ với mỗi truy vấn. Vì phải sử dụng Bignum nên dộ phức tạp là $k^3\ast logn$ với mỗi truy vấn.