Hướng dẫn giải của [VTT Q4 Contest 08] Bài 3: Nhận kẹo [NKEO]
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
Thao tác chuyển một thừa số nguyên tố ~X~ từ phần tử này sang phần tử khác, nên với mỗi số nguyên tố ~p~, tổng số mũ ~S_p~ của ~p~ trên cả dãy không đổi, nhưng ta được phân phối tùy ý giữa các phần tử. Ước chung lớn nhất có số mũ của ~p~ bằng số mũ nhỏ nhất, lớn nhất khi chia đều: ~\lfloor S_p / n \rfloor~.
Sub 1: Phân tích bằng chia thử — ~O(n \sqrt{V})~, dùng khi ~n \le 100~
Với mỗi ~a_i~, chia thử các ~p~ từ 2 đến ~\sqrt{a_i}~, cộng số mũ vào ~S_p~; phần dư lớn hơn 1 là một số nguyên tố. Đáp số là tích các ~p^{\lfloor S_p/n \rfloor}~. Nếu chỉ nộp sub này: đúng 20/20 test (test cục bộ khá dễ dãi; trên máy chấm thật với ~n~ lớn sẽ chậm).
Sub 2: Sàng ước nguyên tố nhỏ nhất — ~O(V \log\log V + n \log V)~
Sàng ~spf[x]~ cho mọi ~x \le 10^6~, rồi phân tích mỗi ~a_i~ bằng cách chia liên tiếp cho ~spf~. Phần còn lại giống sub 1. Đáp số không vượt quá ~10^6~ vì tích của nó chia hết tích ~n~ số, nên tích ~n~ số ít nhất là ~ans^n~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu; ~n \le 100~ gọi sub1, ngược lại gọi sub2. 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;
int a[100005];
int spf[1000001];
long long tot[1000001]; // tổng số mũ của mỗi số nguyên tố trên cả dãy
long long finish() {
// Mỗi số nguyên tố p có tổng số mũ S, chia đều cho n phần tử: mỗi phần tử được S/n
long long ans = 1;
for (int p = 2; p <= 1000000; p++)
for (long long e = tot[p] / n; e > 0; e--) ans *= p;
return ans;
}
// Sub 1: phân tích từng số bằng chia thử đến căn
void sub1() {
for (int i = 0; i < n; i++) {
int x = a[i];
for (int p = 2; (long long)p * p <= x; p++)
while (x % p == 0) { tot[p]++; x /= p; }
if (x > 1) tot[x]++;
}
cout << finish() << "\n";
}
// Sub 2: sàng ước nguyên tố nhỏ nhất, phân tích mỗi số trong O(log)
void sub2() {
for (int i = 2; i <= 1000000; i++)
if (!spf[i])
for (int j = i; j <= 1000000; j += i) if (!spf[j]) spf[j] = i;
for (int i = 0; i < n; i++) {
int x = a[i];
while (x > 1) { tot[spf[x]]++; x /= spf[x]; }
}
cout << finish() << "\n";
}
int main() {
freopen("NKEO.INP", "r", stdin);
freopen("NKEO.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 100) sub1();
else sub2();
}
Bình luận