Cách đơn giản chỉ cần sử dụng thuật toán nhân nhị phân để tính giá trị lũy thừa. ĐPT $O(nlog(m))$, do $n$ rất lớn nên cách này sẽ bị TLE.

Ta có định lý: Với $m$ nguyên dương, biểu thức $P(n)=1^m+2^m+...+n^m$ với có thể biểu diễn dưới dạng một đa thức bậc $m+1$ với mọi $n$ nguyên dương (đa thức Faulhaber).

Từ đó ta sử dụng phương pháp nội suy để tính giá trị đa thức tại một điểm: tính $m+2$ mốc $P(0),P(1),...,P(m+1)$ rồi áp dụng công thức nội suy Lagrange trên lưới đều; phép chia được thay thế bằng phép nhân nghịch đảo (áp dụng định lý Fermat nhỏ) với các hệ số tổ hợp được tính trước.

ĐPT: $O(mlog(p))$ với $p$ là số nguyên tố lấy dư.

Có thể tính các mốc nội suy nhanh hơn bằng cách sử dụng sàng Euler, ĐPT lúc này sẽ là $O(m)$.