Hướng dẫn giải của [TS10 Nam Định 2025 - 2026] Chính phương
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Ý tưởng
Gọi tổng các phần tử là ~S=n~. Với mỗi ~i~, tổng của ~k-1~ phần tử còn lại là ~n-a_i=x_i^2~, nên ~a_i=n-x_i^2~. Từ ~\sum a_i=n~ suy ra ~\sum x_i^2=(k-1)n~. Bài toán trở thành đếm cách chọn ~k~ số chính phương phân biệt nhỏ hơn ~n~ có tổng bằng ~(k-1)n~. Dùng quy hoạch động chọn tập con kiểu knapsack 0/1.
Độ phức tạp
~O(\sqrt n \cdot k^2 \cdot n)~.
Bình luận