Hướng dẫn giải của Đứa trẻ may mắn (KS THCS 04)
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àn hình hiển thị tích của các số đã bấm. Tích là số chính phương khi mọi số nguyên tố đều có số mũ chẵn, nên chỉ cần theo dõi tính chẵn lẻ của số mũ từng số nguyên tố.
Sub 1: Phân tích bằng thử chia — ~O(N \sqrt{A})~, dùng khi ~N \le 500~
Mỗi lần bấm, phân tích số bằng thử chia và đảo tính chẵn lẻ của từng thừa số; đếm số nguyên tố có số mũ lẻ. Nếu chỉ nộp sub này: đúng 6/6 test.
Sub 2: Sàng nguyên tố nhỏ nhất — ~O(A \log \log A + N \log A)~
Sàng số nguyên tố nhỏ nhất đến ~10^6~ để phân tích mỗi số trong ~O(\log A)~. Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Nếu ~N \le 500~ dùng sub 1, còn lại dùng sub 2. 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;
int N;
vector<long long> a; // cac so nguoi choi bam, a[0..N-1]
// Man hinh = tich cac so da bam. Tich la so chinh phuong khi moi so nguyen to co so mu chan.
// Ta theo doi "tinh chan le" cua so mu moi so nguyen to va dem so nguyen to co mu le.
// Sub 1: phan tich moi so bang thu chia tu 2 den can bac hai — dung khi N <= 500
void sub1() {
map<long long, int> par; // par[p] = 1 neu so mu cua p hien tai la le
int odd = 0; // so nguyen to co so mu le
for (int i = 0; i < N; i++) {
long long x = a[i];
auto flip = [&](long long p) {
int &f = par[p];
f ^= 1;
odd += f ? 1 : -1;
};
for (long long p = 2; p * p <= x; p++)
while (x % p == 0) { flip(p); x /= p; }
if (x > 1) flip(x);
cout << (odd == 0 ? "DA" : "NE") << "\n";
}
}
// Sub 2: sang nguyen to den 10^6 de phan tich moi so nhanh O(log a)
void sub2() {
const int MX = 1000000;
vector<int> spf(MX + 1, 0);
for (int i = 2; i <= MX; i++)
if (!spf[i])
for (int j = i; j <= MX; j += i)
if (!spf[j]) spf[j] = i;
vector<char> par(MX + 1, 0);
int odd = 0;
for (int i = 0; i < N; i++) {
int x = a[i];
while (x > 1) {
int p = spf[x];
par[p] ^= 1;
odd += par[p] ? 1 : -1;
x /= p;
}
cout << (odd == 0 ? "DA" : "NE") << "\n";
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> N;
a.assign(N, 0);
for (auto &x : a) cin >> x;
if (N <= 500) sub1();
else sub2();
return 0;
}
Bình luận