Hướng dẫn giải của [VTT Q4 Contest 09] Bài 3: Ước số [DIVISOR]
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
Tìm ước thứ ~k~ (theo thứ tự tăng dần) của ~n~, hoặc in -1 nếu ~n~ có ít hơn ~k~ ước. Ý chính: ước của ~n~ đi theo cặp ~(d, n/d)~ nên chỉ cần xét đến ~\sqrt{n}~, hoặc phân tích thừa số rồi sinh các ước.
Sub 1: Thử mọi số — ~O(n)~, dùng khi ~n \le 10^6~
Duyệt ~d~ từ 1 đến ~n~, đếm các ~d~ chia hết ~n~, dừng khi đếm đến ~k~. Nếu chỉ nộp sub này: đúng 19/20 test (1 test lớn bị quá thời gian).
Sub 2: Duyệt đến căn — ~O(\sqrt{n})~, dùng khi ~n \le 10^9~
Duyệt ~d~ từ 1 đến ~\sqrt{n}~. Mỗi ước nhỏ ~d~ cho thêm ước lớn ~n/d~; các ước nhỏ xuất hiện theo thứ tự tăng, còn các ước lớn xuất hiện theo thứ tự giảm nên cần lưu lại rồi duyệt ngược sau cùng. Bẫy: khi ~n~ là số chính phương thì ~\sqrt{n}~ chỉ được đếm một lần. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 3: Phân tích thừa số nguyên tố — gần ~O(\sqrt{n})~ nhưng nhanh hơn nhiều
Thử chia ~n~ cho ~2, 3, 5, 7, \dots~ chỉ khi ~p^2 \le x~ với ~x~ là phần còn lại (giảm dần khi chia được), phần còn lại lớn hơn 1 là một thừa số nguyên tố. Từ dạng phân tích, sinh mọi ước (tối đa vài chục nghìn ước với ~n \le 10^{15}~), sắp xếp rồi lấy phần tử thứ ~k~. Dùng long long khắp nơi vì ~n~ lên đến ~10^{15}~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc ~n, k~; ~n \le 10^6~ gọi sub1, ~n \le 10^9~ gọi sub2, còn lại gọi sub3. 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. Chương trình đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
long long n, k;
// Sub 1: thử mọi số từ 1 đến n — O(n), dùng khi n <= 10^6
void sub1() {
long long cnt = 0;
for (long long d = 1; d <= n; d++)
if (n % d == 0 && ++cnt == k) { cout << d << "\n"; return; }
cout << -1 << "\n";
}
// Sub 2: ước đi theo cặp (d, n/d), chỉ duyệt d <= sqrt(n) — O(sqrt(n))
void sub2() {
vector<long long> big; // các ước lớn n/d (d < sqrt n)
long long cnt = 0;
for (long long d = 1; d * d <= n; d++) {
if (n % d) continue;
if (++cnt == k) { cout << d << "\n"; return; }
if (d * d != n) big.push_back(n / d);
}
// các ước lớn xuất hiện theo thứ tự giảm dần của d => đảo lại để tăng dần
for (int i = (int)big.size() - 1; i >= 0; i--)
if (++cnt == k) { cout << big[i] << "\n"; return; }
cout << -1 << "\n";
}
// Sub 3: phân tích n ra thừa số nguyên tố (thử chia, n giảm dần nên nhanh hơn),
// sinh toàn bộ ước (tối đa vài chục nghìn), sắp xếp, lấy phần tử thứ k
void sub3() {
vector<long long> dv = {1};
long long x = n;
for (long long p = 2; p * p <= x; p += (p == 2 ? 1 : 2)) {
if (x % p) continue;
int e = 0;
while (x % p == 0) { x /= p; e++; }
size_t sz = dv.size();
long long pw = 1;
for (int i = 1; i <= e; i++) {
pw *= p;
for (size_t j = 0; j < sz; j++) dv.push_back(dv[j] * pw);
}
}
if (x > 1) {
size_t sz = dv.size();
for (size_t j = 0; j < sz; j++) dv.push_back(dv[j] * x);
}
sort(dv.begin(), dv.end());
if (k <= (long long)dv.size()) cout << dv[k - 1] << "\n";
else cout << -1 << "\n";
}
int main() {
freopen("DIVISOR.INP", "r", stdin);
freopen("DIVISOR.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> k;
if (n <= 1000000) sub1();
else if (n <= 1000000000) sub2();
else sub3();
}
Bình luận