Giúp ý tưởng đếm số cách phân tích 1 số nguyên thành tổng 4 bình phương

[sontt (nguyễn thái sơn)]

Người ta đã chứng minh được rằng một số nguyên dương bất kỳ có thể phân rã thành tổng của không quá 4 bình phương của các số nguyên khác. Ví dụ, 12 = 3^2 + 1^2 + 1^2+ 1^2
Tuy vậy đây không phải là cách phân tích duy nhất.

Yêu cầu: Cho số nguyên n (1 ≤ n ≤ 2 500 000). Hãy xác định có có bao nhiêu cách biểu diễn n = a^2 +b^2 +c^2 +d^2 khác nhau, ở đây a, b, c, d là các số nguyên không âm. Hai cách biểu diễn chỉ khác nhau ở trình tự số hạng được là một.

Dữ liệu: Vào từ file văn bản SUM.INP gồm một dòng chứa số nguyên n.

Kết quả: Đưa ra file văn bản SUM.OUT một số nguyên – số cách biểu diễn khác nhau.

Ví dụ:

SUM.INP
12
SUM.OUT
2

---

mk chỉ cần gợi ý cách làm thôi nhé

[noname00 (HK boy)]

Bạn có thể làm được cách 3 vòng for không?

for (int i = 0; i * i <= n; i++)
    for (int j = i; i * i + j * j <= n; j++)
        for (int k = j; i * i + j * j + k * k <= n; k++) {
            // tìm số thứ 4;
        }

[sontt (nguyễn thái sơn)]

nhưng n<=2 500 000 sẽ quá thời gian

[noname00 (HK boy)]

Dùng toán suy luận chút thôi bạn.

n \le 2.5e6,\ n=a^2+b^2+c^2+d^2,\ 0 \le a \le b \le c \le d thì a, b, c, d \le \sqrt{n} < 1582.

Thực hiện 2 vòng for với a, b rồi kiểm tra n - a^2 - b^2 có thể tạo được tổng của 2 bình phương hay không. Bạn cố gắng kiểm tra trong O(\log n) là được.

[sontt (nguyễn thái sơn)]

ok cảm ơn bạn nhiều. thanks