Hướng dẫn giải của Câu 1 (Tuyển sinh chuyên Tin Bình Dương 2022-2023)
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
Đề cho số nguyên K (K ≤ 20000), liệt kê các cặp bạn bè M < N ≤ K, tức là tổng ước thực sự (không tính chính nó) của M bằng N và của N bằng M. Nếu không có cặp nào thì in 0. Ví dụ K = 300 cho cặp 220 284.
Sub 1: Vét cạn — ~O(K^4)~
Với mỗi cặp M < N ≤ K, tính tổng ước thực sự của M và của N bằng cách thử mọi số từ 1 đến x-1 rồi kiểm tra điều kiện. Đúng theo đề nhưng rất chậm khi K lớn.
Đạt 13/20 test, các test K lớn bị quá thời gian.
#include <bits/stdc++.h>
using namespace std;
// Tong uoc so thuc su (tru chinh no) cua x, tinh bang cach thu tat ca so tu 1 den x-1
long long tongUoc(long long x) {
long long s = 0;
for (long long d = 1; d < x; d++)
if (x % d == 0) s += d;
return s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long K;
cin >> K;
int dem = 0;
// Thu moi cap M < N <= K
for (long long M = 1; M <= K; M++)
for (long long N = M + 1; N <= K; N++)
if (tongUoc(M) == N && tongUoc(N) == M) {
cout << M << " " << N << "\n";
dem++;
}
if (dem == 0) cout << 0 << "\n"; // khong co cap nao thi in 0
return 0;
}
Sub 2: Sàng điều hòa — ~O(K log K)~
Tính sẵn s[x] = tổng ước thực sự của x với mọi x ≤ K bằng cách với mỗi d, cộng d vào s[2d], s[3d], … (tổng O(K log K)). Sau đó với mỗi M kiểm tra N = s[M] có N > M, N ≤ K và s[N] = M. Lưu ý s[M] có thể lớn hơn K nên phải kiểm tra N ≤ K trước khi tra mảng.
Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long K;
cin >> K;
// s[x] = tong cac uoc thuc su cua x. Sang kieu harmonic: moi d la uoc cua cac boi x = 2d, 3d, ...
// Thoi gian O(K log K)
vector<long long> s(K + 1, 0);
for (long long d = 1; d <= K; d++)
for (long long x = 2 * d; x <= K; x += d)
s[x] += d;
int dem = 0;
for (long long M = 1; M <= K; M++) {
long long N = s[M]; // N la tong uoc cua M, can N <= K
// Dieu kien: M < N, N <= K va tong uoc cua N bang M
if (N > M && N <= K && s[N] == M) {
cout << M << " " << N << "\n";
dem++;
}
}
if (dem == 0) cout << 0 << "\n"; // khong co cap nao thi in 0
return 0;
}
Bình luận