Hướng dẫn giải của [2627 KS3] Câu 2: Gộp tiền mua vé
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.
Hướng dẫn giải
Đếm cặp ~(i, j)~ với ~i < j~ sao cho ~(a_i + a_j)~ chia hết cho ~k~. Điều kiện tương đương với tổng hai số dư bằng 0 hoặc bằng ~k~ khi chia cho ~k~.
Sub 1: vét cạn mọi cặp — ~O(n^2)~, dùng khi ~n \le 3000~
Thử mọi cặp ~(i, j)~ và đếm. Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: đếm số dư bằng map — ~O(n \log n)~
Duyệt ~j~, với số dư ~r~ của ~a_j~ cần số dư ~(k - r) mod k~ đã gặp trước đó. Dùng map để tránh tạo mảng ~k~ phần tử (~k~ có thể rất lớn). Đúng 20/20 test. Đáp án có thể lớn, dùng long long.
Chương trình hoàn chỉnh
main đọc t và từng chuyến. Nếu ~n \le 3000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
// Dem cap (i<j) co (a_i + a_j) chia het cho k.
// Sub 1: vet can moi cap (i,j). O(n^2). Dung khi n <= 3000.
long long sub1(const vector<long long> &a, long long k) {
long long cnt = 0;
int n = a.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if ((a[i] + a[j]) % k == 0) cnt++;
return cnt;
}
// Sub 2: duyet j, dem so i<j co so du cua a_i bu voi so du cua a_j.
// Dung map de khong phai tao mang k phan tu (k co the lon). O(n log n).
long long sub2(const vector<long long> &a, long long k) {
map<long long, long long> cnt; // so lan xuat hien cua so du
long long ans = 0;
for (long long x : a) {
long long r = x % k;
long long need = (k - r) % k; // so du can ghep voi r de chia het cho k
auto it = cnt.find(need);
if (it != cnt.end()) ans += it->second;
cnt[r]++;
}
return ans;
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
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 ans = (n <= 3000) ? sub1(a, k) : sub2(a, k);
cout << ans << "\n";
}
return 0;
}
Bình luận