Hướng dẫn giải của Cặp số tương đồng
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.
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
, ,
Editorial for samepair: Cặp số tương đồng
Hiểu bài toán
Cho hai số nguyên dương L và R (L < R ≤ 10^6). Hai số A và B được gọi là 'cặp số tương đồng' nếu chúng có chung tập hợp các ước nguyên tố (tức là tập hợp các số nguyên tố phân tử của A và B là như nhau). Yêu cầu đếm số lượng cặp (A, B) sao cho L ≤ A < B ≤ R và A, B là một cặp số tương đồng.
Các cách tiếp cận
Cách Brute Force (Sử dụng map với vector)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int L, R;
cin >> L >> R;
// 1. Sàng SPF (Smallest Prime Factor)
vector<int> spf(R + 1);
for (int i = 1; i <= R; i++) spf[i] = i;
for (int i = 2; i * i <= R; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= R; j += i) {
if (spf[j] == j)
spf[j] = i;
}
}
}
// 2. Gom nhóm theo tập ước nguyên tố
map<vector<int>, long long> cnt;
for (int x = L; x <= R; x++) {
int t = x;
vector<int> primes;
while (t > 1) {
int p = spf[t];
primes.push_back(p);
while (t % p == 0) t /= p;
}
cnt[primes]++; // Tăng đếm cho nhóm
}
// 3. Tính số cặp
long long ans = 0;
for (auto &it : cnt) {
long long k = it.second;
if (k >= 2)
ans += k * (k - 1) / 2;
}
cout << ans;
return 0;
}
- Time Complexity: O((R - L) * K + N log log N) (K là số lượng ước nguyên tố khác nhau, trung bình nhỏ)
- Space Complexity: O(R + (R-L))
Phương pháp này sử dụng một map để nhóm các số có cùng tập ước nguyên tố.
- Sàng SPF để tìm ước nguyên tố nhỏ nhất cho mỗi số.
- Duyệt từ L đến R, phân tích mỗi số x thành các thừa số nguyên tố duy nhất (không lặp) và lưu vào vector. Vector này là key của map.
- Sau khi đếm số lượng số trong mỗi nhóm, dùng công thức tổ hợp chập 2 của mỗi nhóm để tính tổng số cặp.
Cách này đúng nhưng sử dụng
vectorlàm key chomapkhá chậm và tốn bộ nhớ.
Cách Hash Map với Radical
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int spf[1000001];
void sieve(int n) {
for (int i = 1; i <= n; i++) spf[i] = i;
for (int i = 2; i * i <= n; i++) {
if (spf[i] == i) {
for (int j = i * i; j <= n; j += i) {
if (spf[j] == j) spf[j] = i;
}
}
}
}
int get_radical(int n) {
int tich = 1;
while (n > 1) {
int p = spf[n];
tich *= p;
while (n % p == 0) n /= p;
}
return tich;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int l, r;
cin >> l >> r;
sieve(r);
unordered_map<int, ll> cnt;
for (int n = l; n <= r; n++) {
int radical = get_radical(n);
cnt[radical]++;
}
ll count = 0;
for (auto &it : cnt) {
ll k = it.second;
count += k * (k - 1) / 2;
}
cout << count;
return 0;
}
- Time Complexity: O(R log log R)
- Space Complexity: O(R)
Đây là cách tối ưu hóa của Approach 1. Thay vì dùng vector làm key, ta dùng một số nguyên duy nhất được tính bằng cách nhân tất cả các ước nguyên tố khác nhau của số đó (còn gọi là Radical của số).
- Ví dụ: 12 = 2^2 * 3 => Radical = 2 * 3 = 6.
- Hai số có chung tập ước nguyên tố khi và chỉ khi chúng có cùng Radical.
- Sử dụng
unordered_map(hash map) thay chomapđể tăng tốc độ truy cập.
Độ phức tạp tốt hơn do không phải so sánh các vector.
Cách Mảng đếm (Array Counting)
#include <bits/stdc++.h>
#define N 1000000
using namespace std;
int s[N + 5], v[N + 5], l, r;
void sang() {
for(int i = 2; i <= N; i++) {
if(s[i] == 0) {
s[i] = i;
for(int j = i * 2; j <= N; j += i) {
if(s[j] == 0) s[j] = i;
}
}
}
}
int tinh(int x) {
int d = 1;
while(x > 1) {
int p = s[x];
d *= p;
while(x % p == 0) x /= p;
}
return d;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> l >> r;
sang();
for(int i = l; i <= r; i++) {
v[tinh(i)]++;
}
long long kq = 0;
// Radical nhỏ nhất là 1 (số 1), lớn nhất có thể là N (số nguyên tố)
for(int i = 1; i <= N; i++) {
if (v[i] > 1) {
kq += (long long)v[i] * (v[i] - 1) / 2;
}
}
cout << kq;
return 0;
}
- Time Complexity: O(N log log N)
- Space Complexity: O(N)
Đây là cách tối ưu nhất.
- Sàng SPF cho tất cả số đến N (10^6).
- Tính Radical cho các số từ L đến R.
- Sử dụng mảng
v[]để đếm tần suất của các Radical. Kích thước mảng là N+1 vì Radical của một số x ≤ N không bao giờ vượt quá N. - Duyệt mảng
v[]để tính tổng số cặp. Cách này nhanh nhất vì thao tác với mảng thường nhanh hơn map/hash map và tránh được overhead của cấu trúc dữ liệu phức tạp.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O((R - L) * K + N log log N) (K là số lượng ước nguyên tố khác nhau, trung bình nhỏ) | O(R + (R-L)) | Brute Force (Sử dụng map với vector) |
| 2 | O(R log log R) | O(R) | Hash Map với Radical |
| 3 | O(N log log N) | O(N) | Mảng đếm (Array Counting) |
Bài học kinh nghiệm
- Hai số có chung tập ước nguyên tố khi và chỉ khi chúng có cùng 'Radical' (tích của các ước nguyên tố phân tử khác nhau).
- Sử dụng thuật toán Sàng Eratosthenes để tính 'Smallest Prime Factor' (SPF) giúp phân tích một số ra thừa số nguyên tố rất nhanh (O(log n)).
- Bài toán quy về đếm số lượng số trong mỗi nhóm rồi tính tổ hợp chập 2.
Lỗi thường gặp
- Sử dụng
vector<int>làm key chomaphoặcunordered_mapcó thể gây quá tải về thời gian và bộ nhớ so với việc mã hóa thành số nguyên (Radical). - Quên xử lý trường hợp số 1 (Radical = 1) hoặc các số trùng nhau.
- Kiểu dữ liệu lưu kết quả phải là
long longvì số cặp có thể lên tới ~(10^6)^2 / 2.
Bình luận