Hướng dẫn giải của [VT Thiếu nhi] BÀI 11: TRIPLET
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.
Hướng dẫn giải
Đếm bộ ba (A, B, C) nguyên dương với A \le B \le C và A \cdot B \cdot C \le N.
Sub 1: Vét cạn — ~O(N^3)~ (cắt sớm), dùng khi ~N \le 1000~
Duyệt trực tiếp mọi bộ A \le B \le C, đếm những bộ có A \cdot B \cdot C \le N; khi tích vượt N thì dừng vòng lặp C. Các test trong bộ chấm đều có N lớn hơn 1000 nên không có test nào thuộc miền của sub1. Sub1 chỉ được kiểm tra bằng hai ví dụ trong đề (N = 4 cho 5, N = 100 cho 323).
Sub 2 (đầy đủ): Đếm C bằng công thức — ~O(\sqrt{N} \cdot N^{1/3})~ phép lặp
Với A và B cố định, C chạy từ B đến \lfloor N / (A \cdot B) \rfloor, nên có đúng \lfloor N / (A \cdot B) \rfloor - B + 1 cách chọn C (khi số này dương). Duyệt A với A^3 \le N, và B với A \cdot B^2 \le N (để có C \ge B).
Bẫy: đáp số có thể rất lớn (N = 10^{11} cho khoảng 5.7 \cdot 10^{12}), dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc N. Nếu N \le 1000 gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: vet can - duyet truc tiep moi bo ba A <= B <= C, dem nhung bo co A*B*C <= N.
// Dung khi N <= 1000 (khi do A, B, C deu nho).
void sub1() {
long long cnt = 0;
for (long long a = 1; a <= N; a++)
for (long long b = a; b <= N; b++)
for (long long c = b; c <= N; c++) {
if (a * b * c <= N) cnt++;
else break; // c tang thi a*b*c chi tang, dung som
}
cout << cnt << "\n";
}
// Sub 2: day du - voi A, B co dinh, C chay tu B den N/(A*B): dem truc tiep bang cong thuc, khong duyet C.
// Dieu kien A*B*B <= N (C >= B) la gioi han cua B.
void sub2() {
long long cnt = 0;
for (long long a = 1; a * a * a <= N; a++) {
for (long long b = a; a * b * b <= N; b++) {
long long cMax = N / (a * b); // C lon nhat sao cho A*B*C <= N
cnt += cMax - b + 1; // C = B..cMax
}
}
cout << cnt << "\n";
}
int main() {
freopen("TRIPLET.INP", "r", stdin);
freopen("TRIPLET.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
if (N <= 1000) sub1(); // N nho: duyet truc tiep
else sub2();
return 0;
}
Bình luận