Hướng dẫn giải của [KS cụm QL] Câu 2: Đếm cặp số
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 số cặp ~i < j~ sao cho ~A_i~ và ~A_j~ đều là số nguyên tố, với ~N \le 10^6~ và ~A_i \le 10^9~.
Sub 1: Thử từng cặp — ~O(N^2 \sqrt{A})~, dùng khi ~N \le 1000~
Kiểm tra từng số có phải nguyên tố không bằng thử chia, rồi duyệt mọi cặp ~i < j~ và đếm các cặp đều nguyên tố.
Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: Đếm số nguyên tố rồi tổ hợp — ~O(N \log A)~, dùng khi mọi trường hợp còn lại
Đếm số phần tử nguyên tố ~c~ trong dãy, khi đó số cặp là ~c(c-1)/2~. Mỗi số kiểm tra nguyên tố bằng Miller-Rabin với các cơ số 2, 7, 61, đủ đúng với mọi số dưới ~4.7 \cdot 10^9~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề có 3 subtask theo ~N~ và ~A_i~. Sub 1 dùng khi ~N \le 1000~, sub 2 dùng cho các trường hợp còn lại.
Chương trình đọc ~N~ và dãy. Nếu ~N \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Kiem tra nguyen to bang thu chia (dung cho sub 1)
bool laNguyenTo(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
// Sub 1: vet can, voi moi cap i < j kiem tra ca hai deu nguyen to. Dung khi n <= 1000
void sub1() {
long long cnt = 0;
vector<bool> pr(n);
for (int i = 0; i < n; i++) pr[i] = laNguyenTo(a[i]);
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (pr[i] && pr[j]) cnt++;
cout << cnt << "\n";
}
// Kiem tra nguyen to nhanh cho x <= 10^9: Miller-Rabin voi cac co so nho (xac dinh dung voi x < 3.4*10^14)
long long powmod(long long b, long long e, long long m) {
long long r = 1 % m;
b %= m;
while (e > 0) {
if (e & 1) r = r * b % m;
b = b * b % m;
e >>= 1;
}
return r;
}
bool laNguyenToNhanh(long long x) {
if (x < 2) return false;
// Voi x < 4759123141 chi can 3 co so 2, 7, 61 la du
const long long bases[] = {2, 7, 61};
for (long long p : bases) {
if (x % p == 0) return x == p;
}
long long d = x - 1;
int s = 0;
while (d % 2 == 0) { d /= 2; s++; }
for (long long a : bases) {
long long y = powmod(a, d, x);
if (y == 1 || y == x - 1) continue;
bool hop = false;
for (int r = 1; r < s; r++) {
y = y * y % x;
if (y == x - 1) { hop = true; break; }
}
if (!hop) return false;
}
return true;
}
// Sub 2: dem so phan tu nguyen to c, so cap = c*(c-1)/2. Moi so kiem tra O(log) bang Miller-Rabin
void sub2() {
long long c = 0;
for (int i = 0; i < n; i++)
if (laNguyenToNhanh(a[i])) c++;
cout << c * (c - 1) / 2 << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận