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)\).