Hướng dẫn giải của [VTT Q4 Contest 07] Bài 2: Gốc của số nguyên [GOC]
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
Với mỗi ~N \le M~, gốc của ~N~ là tích các ước nguyên tố phân biệt. Ta cần ~N~ có gốc lớn nhất.
Sub 1: Vét cạn — ~O(M \sqrt{M})~, dùng khi ~M \le 1000~
Duyệt mọi ~N~ từ 1 đến ~M~, phân tích thừa số để tính gốc, giữ ~N~ có gốc lớn nhất (khi bằng nhau giữ ~N~ nhỏ hơn). Nếu chỉ nộp sub này: đúng 12/20 test, các test còn lại quá thời gian.
Sub 2: Số không chứa thừa số chính phương — ~O(\text{khoảng cách} \cdot \sqrt{M})~
Gốc của ~N~ không vượt quá ~N~, và bằng ~N~ khi và chỉ khi ~N~ không chia hết cho bình phương nào (squarefree). Vậy gốc lớn nhất chính là số squarefree lớn nhất không vượt quá ~M~, và số đó cũng là ~N~ cần tìm (các ~N~ không squarefree có gốc nhỏ hơn ~N~, nên không thể bằng gốc này mà nhỏ hơn). Ta lùi dần từ ~M~ cho tới khi gặp số squarefree; khoảng lùi rất nhỏ (vì cứ vài số liên tiếp là có một số squarefree), mỗi lần kiểm tra thử chia các ~p^2 \le N~ mất ~O(\sqrt{N})~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~M~; nếu ~M \le 1000~ 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;
long long M;
// Tính gốc của x bằng phân tích thừa số
long long goc(long long x) {
long long r = 1;
for (long long p = 2; p * p <= x; p++) {
if (x % p == 0) {
r *= p;
while (x % p == 0) x /= p;
}
}
if (x > 1) r *= x;
return r;
}
// Sub 1: duyệt mọi N <= M, lấy N có gốc lớn nhất (cùng gốc thì lấy N nhỏ nhất)
void sub1() {
long long best = 0, ans = 1;
for (long long n = 1; n <= M; n++) {
long long g = goc(n);
if (g > best) { best = g; ans = n; }
}
cout << ans << "\n";
}
// Sub 2: đáp án là số không chứa thừa số chính phương lớn nhất không vượt quá M
bool squarefree(long long x) {
for (long long p = 2; p * p <= x; p++) {
if (x % (p * p) == 0) return false;
}
return true;
}
void sub2() {
long long n = M;
while (!squarefree(n)) n--;
cout << n << "\n";
}
int main() {
freopen("GOC.INP", "r", stdin);
freopen("GOC.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> M;
if (M <= 1000) sub1();
else sub2();
}
Bình luận