Hướng dẫn giải của Bộ số bạn bè (đề Quảng Trị 2020-2021)
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.
Hướng dẫn giải
Đếm số bộ ba (A, B, C) nguyên dương thỏa A×B + C = N. Với mỗi cặp (A, B) có A×B < N thì C = N − A×B là đúng một giá trị hợp lệ, nên bài toán trở thành đếm các cặp (A, B) có A×B ≤ N − 1.
Sub 1: Vét cạn ba vòng lặp — ~O(n^3)~
Thử mọi bộ (A, B, C) với A, B, C từ 1 đến N rồi kiểm tra A×B + C = N. Đạt 10/20 test, 10 test còn lại quá giờ vì N lên tới 10^6.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BSBB.INP", "r")) { freopen("BSBB.INP", "r", stdin); freopen("BSBB.OUT", "w", stdout); }
long long n;
cin >> n;
// Vét cạn: thử mọi bộ (A, B, C) với A, B, C từ 1 đến N
long long cnt = 0;
for (long long a = 1; a <= n; a++)
for (long long b = 1; b <= n; b++)
for (long long c = 1; c <= n; c++)
if (a * b + c == n) cnt++;
cout << cnt << "\n";
return 0;
}
Sub 2: Bỏ vòng lặp C — ~O(n \log n)~
C được xác định ngay từ A và B nên chỉ cần hai vòng lặp, và vòng lặp B dừng khi A×B ≥ N. Tổng số lần lặp là khoảng N·(1 + 1/2 + 1/3 + ...) ≈ N ln N. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BSBB.INP", "r")) { freopen("BSBB.INP", "r", stdin); freopen("BSBB.OUT", "w", stdout); }
long long n;
cin >> n;
// Với mỗi cặp (A, B) mà A*B < N thì C = N - A*B >= 1 là duy nhất
long long cnt = 0;
for (long long a = 1; a < n; a++)
for (long long b = 1; a * b < n; b++)
cnt++;
cout << cnt << "\n";
return 0;
}
Sub 3: Đếm theo A — ~O(n)~
Với A cố định, B chạy từ 1 đến ⌊(N−1)/A⌋ nên có đúng ⌊(N−1)/A⌋ bộ. Cộng dồn theo A từ 1 đến N − 1 là ra đáp án. Đáp án có thể lên tới khoảng N ln N nên dùng long long. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("BSBB.INP", "r")) { freopen("BSBB.INP", "r", stdin); freopen("BSBB.OUT", "w", stdout); }
long long n;
cin >> n;
// Với A cố định, B*A <= N-1 nên có floor((N-1)/A) giá trị B, C được xác định duy nhất
long long cnt = 0;
for (long long a = 1; a < n; a++)
cnt += (n - 1) / a;
cout << cnt << "\n";
return 0;
}
Bình luận