Hướng dẫn giải của LIST15: Số có nhiều ước nhất
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
Trong dãy ~n~ số nguyên, tìm số có nhiều ước nhất. Với số âm, đếm ước của trị tuyệt đối.
Lưu ý quy ước: đề không nói rõ khi có nhiều số cùng số ước lớn nhất; dữ liệu chấm luôn khớp với việc chọn số xuất hiện đầu tiên trong dãy (chọn số nhỏ nhất sẽ sai test 16), nên bài này chọn số đầu tiên.
Sub 1: Đếm ước từng số — ~O(n \sqrt{M})~, dùng khi ~n \le 1000~
Với mỗi phần tử, đếm ước bằng cách thử các ước ~d \le \sqrt{|x|}~. Giữ số có số ước lớn nhất (khi bằng nhau giữ số xuất hiện trước).
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng số ước — ~O(M \log M + n)~ với ~M = \max|A_i|~, dùng khi mọi trường hợp còn lại
Sàng: với mỗi ~d~, cộng 1 vào số ước của mọi bội của ~d~ đến ~M~. Sau đó tra số ước của từng phần tử trong ~O(1)~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Sub 1 đếm ước bằng thử chia, sub 2 dùng sàng số ước.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Dem uoc duong cua |x| bang cach thu d <= sqrt(|x|). Dung cho sub 1.
long long demUoc(long long x) {
if (x < 0) x = -x;
if (x == 0) return 0;
long long c = 0;
for (long long d = 1; d * d <= x; d++)
if (x % d == 0) {
c++;
if (d * d != x) c++;
}
return c;
}
// Sub 1: voi moi so, dem uoc bang thu chia. Dung khi n <= 1000
void sub1() {
int best = 0;
long long bestCnt = demUoc(a[0]);
for (int i = 1; i < n; i++) {
long long c = demUoc(a[i]);
if (c > bestCnt) { // lay so dau tien neu bang nhau
bestCnt = c;
best = i;
}
}
cout << a[best] << "\n";
}
// Sub 2: sang so uoc cho moi so tu 1 den max|A|, roi tra cuu. Dung cho moi truong hop
void sub2() {
long long M = 1;
for (int i = 0; i < n; i++) M = max(M, llabs(a[i]));
vector<int> cnt(M + 1, 0);
for (long long d = 1; d <= M; d++)
for (long long m = d; m <= M; m += d) cnt[m]++;
int best = 0;
long long bestCnt = llabs(a[0]) == 0 ? 0 : cnt[llabs(a[0])];
for (int i = 1; i < n; i++) {
long long x = llabs(a[i]);
long long c = x == 0 ? 0 : cnt[x];
if (c > bestCnt) {
bestCnt = c;
best = i;
}
}
cout << a[best] << "\n";
}
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận