Hướng dẫn giải của [HueICT 2026] Dãy ước số
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.
Gợi ý lời giải
Ý tưởng
Ta không nên tạo trực tiếp toàn bộ dãy ~D~, vì tổng số phần tử của ~D~ có thể rất lớn.
Gọi ~cnt[v]~ là số lần giá trị ~v~ xuất hiện trong mảng ~A~.
Khi đó, với mỗi ~d~, số lần ~d~ xuất hiện trong dãy ~D~ là:
~freq[d] = \sum_{k \text{ là bội của } d} cnt[k]~
vì ~d~ sẽ là ước của đúng các số là bội của ~d~.
Sau khi biết ~freq[d]~ cho mọi ~d~, ta tính mảng cộng dồn:
~pref[d] = freq[1] + freq[2] + \cdots + freq[d]~
Khi đó, câu trả lời cho truy vấn ~x~ là giá trị nhỏ nhất ~d~ sao cho:
~pref[d] \ge x~
Ta tìm bằng lower_bound.
Độ phức tạp
Gọi ~M = \max(A_i)~.
- Tính ~freq~ bằng cách duyệt các bội số: ~O(M \log M)~
- Mỗi truy vấn: ~O(\log M)~
Tổng cộng: ~O(M \log M + Q \log M)~, với ~M \le 10^6~ là đủ tốt.
Code C++ tham khảo
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
cin >> N >> Q;
vector<int> A(N);
int M = 0;
for (int i = 0; i < N; i++) {
cin >> A[i];
M = max(M, A[i]);
}
vector<long long> cnt(M + 1, 0), freq(M + 1, 0), pref(M + 1, 0);
for (int x : A) cnt[x]++;
for (int d = 1; d <= M; d++) {
for (int m = d; m <= M; m += d) {
freq[d] += cnt[m];
}
}
for (int d = 1; d <= M; d++) {
pref[d] = pref[d - 1] + freq[d];
}
while (Q--) {
long long x;
cin >> x;
int ans = lower_bound(pref.begin() + 1, pref.end(), x) - pref.begin();
cout << ans << '\n';
}
return 0;
}
Bình luận