Hướng dẫn giải của Đếm các ước của 1 số nguyên
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu đếm số lượng ước nguyên dương của một số nguyên dương n, với n có thể lên tới 10^18. Ví dụ: với n = 4, các ước là 1, 2, 4 => đáp án là 3.
Các cách tiếp cận
Cách Phân tích thừa số nguyên tố (Prime Factorization)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mul_mod(ull a, ull b, ull mod) {
return (__uint128_t)a * b % mod;
}
ull pow_mod(ull a, ull d, ull mod) {
ull res = 1;
while (d) {
if (d & 1) res = mul_mod(res, a, mod);
a = mul_mod(a, a, mod);
d >>= 1;
}
return res;
}
bool is_prime(ull n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
ull d = n - 1;
int s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
static const ull bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (ull a : bases) {
if (a >= n) break;
ull x = pow_mod(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int r = 0; r < s - 1; r++) {
x = mul_mod(x, x, n);
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
ull pollard_rho(ull n) {
if (n == 1) return 1;
if (n % 2 == 0) return 2;
ull x = 2 + rand() % (n - 2);
ull y = x;
ull c = 1 + rand() % (n - 1);
ull d = 1;
while (d == 1) {
x = (mul_mod(x, x, n) + c) % n;
y = (mul_mod(y, y, n) + c) % n;
y = (mul_mod(y, y, n) + c) % n;
d = __gcd(x > y ? x - y : y - x, n);
if (d == n) return pollard_rho(n);
}
return d;
}
void factorize(ull n, map<ull, int> &factors) {
if (n == 1) return;
if (is_prime(n)) {
factors[n]++;
return;
}
ull divisor = pollard_rho(n);
factorize(divisor, factors);
factorize(n / divisor, factors);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ull n;
if (cin >> n) {
map<ull, int> factors;
factorize(n, factors);
ull ans = 1;
for (auto p : factors) {
ans *= (p.second + 1);
}
cout << ans << endl;
}
return 0;
}
- Time Complexity: O(n^(1/4))
- Space Complexity: O(log n)
Đây là phương pháp tối ưu nhất để giải quyết bài toán này với n lớn. Chúng ta cần phân tích n thành các thừa số nguyên tố (prime factorization). Do n có thể lên tới 10^18, việc kiểm tra chia hết thông thường (O(sqrt(n))) là không khả thi. Thay vào đó, chúng ta kết hợp:
- Miller-Rabin Primality Test: Thử nghiệm tính chất lượng của n với các cơ số nhỏ để kiểm tra xem n có phải là số nguyên tố không. Đây là kiểm tra xác suất, nhưng với các cơ số cố định cho 64-bit, nó trở thành xác định.
- Pollard's Rho Algorithm: Nếu n không phải là số nguyên tố, thuật toán này tìm một thừa số không tầm thường của n một cách nhanh chóng (trung bình O(n^(1/4)).
- Đệ quy: Phân tích cả hai thừa số tìm được cho đến khi tất cả đều là số nguyên tố.
- Công thức đếm ước: Sau khi có các thừa số nguyên tố n = p1^a1 * p2^a2 * ... * pk^ak, số lượng ước là (a1 + 1) * (a2 + 1) * ... * (ak + 1).
Cần cẩn thận với số học để tránh tràn số (sử dụng _int128 hoặc _uint128_t cho phép nhân và modulo).
Cách Tối ưu hóa Brute Force (chỉ kiểm tra ước)
#include <iostream>
#include <cmath>
using namespace std;
int main() {
unsigned long long n;
if (cin >> n) {
unsigned long long count = 0;
unsigned long long root = sqrt(n);
for (unsigned long long i = 1; i <= root; i++) {
if (n % i == 0) {
if (i * i == n) {
count += 1;
} else {
count += 2;
}
}
}
cout << count << endl;
}
return 0;
}
- Time Complexity: O(sqrt(n))
- Space Complexity: O(1)
Đây là phương pháp đơn giản nhất, duyệt từ 1 đến căn bậc hai của n. Nếu i chia hết n thì i và n/i là hai ước. Nếu i*i = n thì đó là ước kép (chỉ tính 1 lần). Với n = 10^18, sqrt(n) = 10^9. Vòng lặp này sẽ chạy khoảng 1 tỷ lần. Trong C++, một phép chia hết và cộng trừ có thể mất khoảng 1-2ns nếu tối ưu, nhưng thường sẽ chậm hơn. Với giới hạn thời gian thường là 1s, phương pháp này có nguy cơ bị TLE (Time Limit Exceeded) cao, hoặc chỉ qua được nếu test case nhẹ và máy chạy nhanh. Tuy nhiên, với n = 10^18, nó chắc chắn không đủ nhanh.
Cách Tối ưu hóa Brute Force kết hợp Pollard's Rho (Khác biệt)
// Ý tưưởng này thực chất là cách tiếp cận 1.
// Để minh họa sự khác biệt, ta xem xét việc chỉ dùng Pollard's Rho để tìm ước.
// Tuy nhiên, cách 1 là chuẩn xác nhất.
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull mul_mod(ull a, ull b, ull mod) {
return (__uint128_t)a * b % mod;
}
ull pollard_rho(ull n) {
if (n % 2 == 0) return 2;
ull x = 2, y = 2, d = 1, c = 1;
auto f = [&](ull x) { return (mul_mod(x, x, n) + c) % n; };
while (d == 1) {
x = f(x);
y = f(f(y));
d = __gcd(x > y ? x - y : y - x, n);
}
if (d == n) return pollard_rho(n); // Retry
return d;
}
int main() {
ull n;
cin >> n;
ull ans = 1;
while (n > 1) {
if (n % 2 == 0) {
int cnt = 0;
while (n % 2 == 0) { n /= 2; cnt++; }
ans *= (cnt + 1);
continue;
}
if (n == 1) break;
ull d = pollard_rho(n);
if (d == n) {
// n is prime
ans *= 2; // exponent is 1, so (1+1) = 2
break;
}
}
cout << ans << endl;
return 0;
}
// Lưu ý: Code trên chưa hoàn chỉnh vì chưa thực sự đếm đúng số mũ của các thừa số.
// Thực tế, Pollard's Rho dùng để tìm ước, sau đó phải kết hợp với kiểm tra nguyên tố.
- Time Complexity: O(n^(1/4))
- Space Complexity: O(log n)
Phương pháp này sử dụng Pollard's Rho để phân tích n. Tuy nhiên, để đếm ước chính xác, ta cần phân tích đầy đủ ra các thừa số nguyên tố. Quy trình:
- Xử lý các thừa số 2.
- Dùng Pollard's Rho để tìm một thừa số d của n.
- Nếu d là n (Pollard's Rho không tìm được ước nhỏ hơn), n là số nguyên tố.
- Nếu tìm được d, ta cần kiểm tra xem d và n/d có phải số nguyên tố không (dùng Miller-Rabin) hoặc tiếp tục phân tích chúng.
- Gom nhóm các thừa số giống nhau và tính tổng số lượng ước.
Đây về cơ bản là cách tiếp cận 1, chỉ khác ở chỗ cách viết có thể chưa tối ưu hóa việc đếm số mũ.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^(1/4)) | O(log n) | Phân tích thừa số nguyên tố (Prime Factorization) |
| 2 | O(sqrt(n)) | O(1) | Tối ưu hóa Brute Force (chỉ kiểm tra ước) |
| 3 | O(n^(1/4)) | O(log n) | Tối ưu hóa Brute Force kết hợp Pollard's Rho (Khác biệt) |
Bài học kinh nghiệm
- Với n <= 10^18, thuật toán O(sqrt(n)) quá chậm, cần dùng đến các thuật toán xác suất/ngẫu nhiên (Probabilistic Algorithms).
- Công thức đếm ước từ thừa số nguyên tố: d(n) = (a1+1)(a2+1)... là chìa khóa.
- Sử dụng _int128 (GCC) hoặc _uint128_t là bắt buộc khi thực hiện các phép nhân modulo với số lớn (tránh tràn số 64-bit).
Lỗi thường gặp
- Quên sử dụng phép nhân an toàn (modular multiplication) dẫn đến tràn số 64-bit khi tính a*b % mod với a, b ~ 10^18.
- Lầm tưởng thuật toán O(sqrt(n)) có thể chạy qua trong 1s với n=10^18 (thực tế cần ~10^9 thao tác, quá chậm).
- Sai lệch trong Miller-Rabin (ví dụ: không chia hết 2, cách tính lũy thừa modulo sai).
Bình luận