Hướng dẫn cho Tích bằng K
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Tóm tắt đề bài
Cho dãy số nguyên \(A\) gồm \(n\) phần tử và một số nguyên \(k\). Đếm số lượng cặp chỉ số \((i, j)\) sao cho \(1 \leq i < j \leq n\) và \(A_i \cdot A_j = k\).
Phân tích
- Điều kiện: \(n \leq 10^5\), \(|A_i|, |k| \leq 10^9\).
- Nhận xét:
- Với \(n = 10^5\), một thuật toán có độ phức tạp \(O(n^2)\) sẽ không kịp thời gian (vì \(10^{10}\) phép tính). Chúng ta cần một giải pháp tối ưu hơn, khoảng \(O(n)\) hoặc \(O(n \log n)\).
- Tích \(A_i \cdot A_j = k\) có thể xảy ra khi một trong hai số là \(0\) (nếu \(k=0\)), hoặc cả hai số đều khác \(0\).
- Vì \(|A_i|, |k|\) lớn, ta cần sử dụng kiểu dữ liệu số nguyên 64-bit (
long longtrong C++,inttrong Python) để tránh tràn số khi tính tích. - Cặp \((i, j)\) với \(i < j\) có nghĩa là chúng ta đếm cặp không tính thứ tự.
Cách làm đơn giản (Brute Force)
Ý tưởng
Sử dụng hai vòng lặp lồng nhau để duyệt qua mọi cặp \((i, j)\) và kiểm tra xem tích của chúng có bằng \(k\) hay không.
Độ phức tạp
- Thời gian: \(O(n^2)\)
- Đánh giá: Chỉ phù hợp với \(n \leq 5000\). Với \(n = 10^5\), cách này sẽ bị quá thời gian (TLE).
Code Brute Force
C++
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
long long k;
cin >> n >> k;
vector<long long> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] * a[j] == k) {
count++;
}
}
}
cout << count << endl;
return 0;
}
Python
Python
n, k = map(int, input().split())
a = list(map(int, input().split()))
count = 0
for i in range(n):
for j in range(i + 1, n):
if a[i] * a[j] == k:
count += 1
print(count)
Hướng giải quyết (Tối ưu)
Ý tưởng
Thay vì duyệt từng cặp, ta đếm số lần xuất hiện của từng giá trị trong mảng bằng một cấu trúc dữ liệu bảng băm (như map trong C++ hoặc dict trong Python).
-
Trường hợp \(k = 0\):
- Tích \(A_i \cdot A_j = 0\) khi có ít nhất một trong hai số bằng \(0\).
- Gọi \(z\) là số lượng số \(0\) trong mảng, \(non\_z\) là số lượng các số khác \(0\).
- Số cặp gồm một số \(0\) và một số khác \(0\) là: \(z \cdot non\_z\).
- Số cặp gồm hai số \(0\) là: \(\frac{z \cdot (z - 1)}{2}\).
- Tổng số cặp là: \(z \cdot non\_z + \frac{z \cdot (z - 1)}{2}\).
-
Trường hợp \(k \neq 0\):
- Ta duyệt qua từng giá trị \(v\) duy nhất trong bảng tần suất.
- Nếu \(k\) chia hết cho \(v\), ta cần tìm giá trị \(target = k / v\).
- Nếu \(v < target\): Số cặp được tạo ra là \(count(v) \cdot count(target)\).
- Nếu \(v = target\): Số cặp được tạo ra là \(\frac{count(v) \cdot (count(v) - 1)}{2}\).
- Lưu ý: Chỉ xét \(v \neq 0\) vì \(k \neq 0\).
Các bước thực hiện
- Đếm tần suất xuất hiện của các số trong mảng \(A\) và lưu vào một
map. - Áp dụng công thức đếm dựa trên giá trị của \(k\) như trên.
Độ phức tạp
- Thời gian: \(O(n \log n)\) nếu dùng
std::map(C++) hoặc \(O(n)\) nếu dùngunordered_map/dict(Python). - Bộ nhớ: \(O(n)\) để lưu trữ bảng tần suất.
Code tham khảo
C++
C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long k;
cin >> n >> k;
map<long long, long long> freq;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
freq[x]++;
}
long long ans = 0;
if (k == 0) {
long long z = freq[0];
long long non_z = n - z;
// Cặp (0, số khác 0) và cặp (0, 0)
ans = z * non_z + z * (z - 1) / 2;
} else {
for (auto const& [v, countV] : freq) {
if (v == 0 || k % v != 0) continue;
long long target = k / v;
if (freq.count(target)) {
if (v < target) {
ans += countV * freq[target];
} else if (v == target) {
ans += countV * (countV - 1) / 2;
}
}
}
}
cout << ans << endl;
return 0;
}
Python
Python
import sys
def solve():
# Đọc dữ liệu nhanh
input_data = sys.stdin.read().split()
if not input_data:
return
n = int(input_data[0])
k = int(input_data[1])
a = list(map(int, input_data[2:]))
freq = {}
for x in a:
freq[x] = freq.get(x, 0) + 1
ans = 0
if k == 0:
z = freq.get(0, 0)
non_z = n - z
ans = z * non_z + z * (z - 1) // 2
else:
# Lấy danh sách các khóa để duyệt
keys = list(freq.keys())
for v in keys:
if v == 0 or k % v != 0:
continue
target = k // v
if target in freq:
if v < target:
ans += freq[v] * freq[target]
elif v == target:
ans += freq[v] * (freq[v] - 1) // 2
print(ans)
if __name__ == "__main__":
solve()
Bình luận