Hướng dẫn giải của Đếm ước (đề HSG 9 Phú Thọ 2022-2023)
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
Với số tự nhiên n (1 <= n <= 10^6), tìm số tự nhiên nhỏ hơn n có nhiều ước thực sự nhất (ước d với d < x). Nếu có nhiều số thỏa mãn thì in số nhỏ nhất.
Sub 1: Đếm ước từng số bằng thử chia — ~O(n \sqrt{n})~, dùng khi ~n \le 10^4~
Với mỗi x < n, đếm các ước d của x (d < x) bằng cách thử chia đến căn bậc hai. Cập nhật đáp án khi số đếm được lớn hơn thật sự, nên giữ được số nhỏ nhất khi bằng nhau.
Nếu chỉ nộp sub này: đúng 48/50 test (2 test có n lớn bị quá giờ).
Sub 2: Sàng ước — ~O(n \log n)~
Với mỗi d từ 1, cộng 1 vào cnt[m] cho mọi bội m = 2d, 3d, ... nhỏ hơn n. Khi đó cnt[m] chính là số ước thực sự của m. Sau đó quét x từ 1 đến n-1 và giữ số đầu tiên đạt số đếm lớn nhất.
Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
Main đọc n từ bàn phím. Nếu n <= 10^4 gọi sub1, ngược lại gọi sub2. In kết quả ra màn hình.
#include <bits/stdc++.h>
using namespace std;
int n;
// Sub 1: voi moi x < n, dem uoc thuc su (uoc d < x) bang thu chia den can bac hai — O(n sqrt n), dung khi n <= 10^4
void sub1() {
int best = 1, bestCnt = 0; // x = 1 co 0 uoc thuc su
for (int x = 1; x < n; x++) {
int cnt = 0;
for (int d = 1; (long long)d * d <= x; d++) {
if (x % d == 0) {
if (d < x) cnt++;
int e = x / d;
if (e != d && e < x) cnt++;
}
}
if (cnt > bestCnt) { best = x; bestCnt = cnt; } // chi cap nhat khi lon hon de giu so nho nhat
}
cout << best << "\n";
}
// Sub 2: sang uoc — voi moi d, cong 1 cho cac boi m = 2d, 3d, ... (< n) — O(n log n)
void sub2() {
vector<int> cnt(n + 1, 0);
for (int d = 1; d < n; d++)
for (int m = 2 * d; m < n; m += d)
cnt[m]++;
int best = 1, bestCnt = 0;
for (int x = 1; x < n; x++)
if (cnt[x] > bestCnt) { best = x; bestCnt = cnt[x]; }
cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
if (n <= 10000) sub1();
else sub2();
return 0;
}
Bình luận