Hướng dẫn giải của Nhân tố (đề KS2 ĐH 2024)
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
Nhân tố lớn nhất là ~p^x~ lớn nhất trong các thừa số nguyên tố ~p^x~ của ~N~. Chỉ cần tách hết thừa số nguyên tố của ~N~ rồi lấy giá trị lớn nhất.
Sub 1: Thử chia mọi số — ~O(N)~, dùng khi ~N \le 10^6~
Thử từng ~d~ từ 2 đến ~N~. Nếu ~d~ chia hết phần còn lại thì ~d~ là số nguyên tố (các ước nhỏ hơn đã được loại), tách hết mũ và tính ~d^x~.
Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Thử chia đến căn bậc hai — ~O(\sqrt{N})~
Chỉ thử ~d~ đến ~\sqrt{N}~. Phần còn lại sau khi chia (nếu lớn hơn 1) là số nguyên tố có mũ 1, cũng là một nhân tố.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Dữ liệu ~N \le 10^6~ dùng sub 1, còn lại dùng sub 2. Bẫy: ~p^x~ có thể lên đến ~10^{12}~ nên dùng long long.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: vet can O(N). Thu moi d tu 2 den N: neu d chia het N thi d la uoc nguyen to
// (cac uoc nho hon da duoc loai het). Lay mu roi lay gia tri p^x lon nhat. Dung khi N <= 10^6.
void sub1() {
long long n = N, best = 1;
for (long long d = 2; d <= n; d++) {
if (n % d == 0) {
long long v = 1, x = 0;
while (n % d == 0) { n /= d; x++; v *= d; }
best = max(best, v);
}
}
cout << best << "\n";
}
// Sub 2: chia thu den can bac hai, O(sqrt(N)). Phan con lai (neu > 1) la so nguyen to co mu 1.
void sub2() {
long long n = N, best = 1;
for (long long d = 2; d * d <= n; d++) {
if (n % d == 0) {
long long v = 1;
while (n % d == 0) { n /= d; v *= d; }
best = max(best, v);
}
}
if (n > 1) best = max(best, n);
cout << best << "\n";
}
int main() {
cin >> N;
if (N <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận