[Nam Định - TS10 - 2025] Bài 4: Chính phương
Xem dạng PDF
Gửi bài giải
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
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; }
}
int main() { // Tối ưu hóa tốc độ nhập/xuất C++ iosbase::syncwith_stdio(false); cin.tie(NULL);
}