Lời giải

Xét mọi cặp cần ~n^2/2 = 4.5 \cdot 10^{10}~ phép tính nên quá thời gian.

Mấu chốt là nhân hai vế với ~(a_i - a_j)~. Vì các ~a_i~ đôi một khác nhau và ~p~ là số nguyên tố nên ~a_i - a_j \not\equiv 0~, phép nhân này không làm mất nghiệm. Khi đó vế trái trở thành

~(a_i - a_j)(a_i + a_j)(a_i^2 + a_j^2) = (a_i^2 - a_j^2)(a_i^2 + a_j^2) = a_i^4 - a_j^4~

nên điều kiện tương đương với ~a_i^4 - a_j^4 \equiv k(a_i - a_j)~, hay

~a_i^4 - k \cdot a_i \equiv a_j^4 - k \cdot a_j \pmod p~

Vậy chỉ cần tính ~h_i = (a_i^4 - k a_i) \bmod p~ cho mỗi ~i~, rồi đếm số cặp có cùng giá trị ~h~.