[Nam Định - TS10 - 2025] Bài 4: Chính phương

Xem dạng PDF

Gửi bài giải

Điểm: 35,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Một tập hợp ~A = {a_1, \ldots, a_k}~ gồm ~k~ số tự nhiên khác nhau có tổng các phần tử là ~n~ gọi là tập sinh chính phương nếu tổng của bất kỳ ~k - 1~ phần tử trong ~A~ đều là số chính phương.

Yêu cầu: Cho hai số nguyên ~n~ và ~k~. Đếm số tập hợp ~A~ gồm ~k~ phần tử có tổng các phần tử bằng ~n~ và tổng của ~k - 1~ phần tử bất kỳ trong tập này đều là số chính phương.

INPUT
  • Một dòng duy nhất gồm ~2~ số nguyên dương ~n, k~ ~(2 \leq n \leq 10^4, 2 \leq k \leq 10)~
OUTPUT
  • Một dòng duy nhất là kết quả bài toán
SAMPLE INPUT
20 2
SAMPLE OUTPUT
1
SUBTASKS
Subtask Điểm Ràng buộc
1 ~25%~ ~k = 2~
2 ~50%~ ~k = 3~
3 ~25%~ ~k \le 10~

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    UIAA  đã bình luận lúc 9, Tháng 11, 2026, 8:02

    include <iostream>

    include <cmath>

    using namespace std;

    int n, k; int target; int max_x; long long ans = 0;

    // Hàm quay lui tìm các giá trị x // idx: số lượng phần tử x đã chọn (từ 0 đến k-1) // currentsum: tổng bình phương hiện tại của các x đã chọn // lastval: giá trị x của bước trước (để đảm bảo x1 < x2 < ... < xk) void backtrack(int idx, int currentsum, int lastval) { // Nếu đã chọn đủ k phần tử if (idx == k) { if (currentsum == target) { ans++; } return; }

    // Nhánh cận 1: Kiểm tra xem tổng hiện tại cộng với số nhỏ nhất có thể cho các ô còn lại có vượt quá target không, 
    // hoặc cộng với số lớn nhất có thể có đủ đạt được target không.
    int remaining = k - idx;
    
    // Vòng lặp duyệt các giá trị x tiếp theo
    for (int x = last_val + 1; x <= max_x; ++x) {
        int x2 = x * x;
    
        // Nếu tổng hiện tại + x^2 vượt quá target thì dừng (vì x tăng dần, các x sau còn lớn hơn)
        if (current_sum + x2 > target) {
            break;
        }
    
        // Nhánh cận bổ sung: Nếu tổng lớn nhất có thể tạo ra từ các phần tử còn lại (bao gồm cả x) 
        // mà vẫn nhỏ hơn target thì ta có thể bỏ qua nhánh này.
        // Tuy nhiên, do vòng lặp duyệt tăng dần, ta xét thêm điều kiện chặn dưới/chặn trên nếu cần.
        // Ở đây điều kiện current_sum + x2 + (remaining - 1) * max_x^2 < target có thể dùng để cắt tỉa phía dưới.
        // Nhưng với n <= 10000 và k <= 10, việc dừng sớm khi vượt quá target đã rất tối ưu rồi.
    
        backtrack(idx + 1, current_sum + x2, x);
    }
    

    }

    int main() { // Tối ưu hóa tốc độ nhập/xuất C++ iosbase::syncwith_stdio(false); cin.tie(NULL);

    // Đọc dữ liệu từ chuẩn (hoặc thay bằng file nếu dùng trong môi trường thi chấm file)
    // freopen("CHINHPHUONG.INP", "r", stdin);
    // freopen("CHINHPHUONG.OUT", "w", stdout);
    
    if (!(cin >> n >> k)) return 0;
    
    target = (k - 1) * n;
    // Vì a_i = n - x_i^2 >= 0 => x_i^2 < n => x_i <= sqrt(n - 1)
    max_x = sqrt(n - 1);
    
    backtrack(0, 0, -1);
    
    cout << ans << "\n";
    
    return 0;
    

    }