Hướng dẫn giải của Số nguyên tố đơn điệu (Đề Long An 2021)
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ột số là "nguyên tố đơn điệu" khi nó là số nguyên tố, có ít nhất hai chữ số, và các chữ số của nó luân phiên tăng rồi giảm (hoặc giảm rồi tăng). Cần đếm trong dãy có bao nhiêu số như vậy. Các số đều nhỏ hơn 10^6 và dãy có N ≤ 20 phần tử nên có thể kiểm tra từng số.
Sub 1: Vét cạn — ~O(N \cdot a)~
Với mỗi số a, kiểm tra nguyên tố bằng cách thử mọi ước d từ 2 đến a - 1. Sau đó chuyển a thành chuỗi chữ số, kiểm tra hai chữ số liên tiếp khác nhau và mỗi bộ ba chữ số liên tiếp có chiều tăng/giảm đổi chiều. Đếm các số thỏa mãn cả hai điều kiện.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LONGAN.INP", "r")) { freopen("LONGAN.INP", "r", stdin); freopen("LONGAN.OUT", "w", stdout); }
int n;
cin >> n;
int cnt = 0;
for (int t = 0; t < n; t++) {
long long a;
cin >> a;
// Kiem tra nguyen to bang cach thu moi uoc tu 2 den a-1 (vet can)
bool prime = a >= 2;
for (long long d = 2; d < a && prime; d++)
if (a % d == 0) prime = false;
if (!prime) continue;
// Chuyen so thanh chuoi chu so de kiem tra luan phien tang giam
string s = to_string(a);
bool zig = s.size() >= 2;
// Hai chu so lien tiep phai khac nhau
for (size_t i = 0; i + 1 < s.size() && zig; i++)
if (s[i] == s[i + 1]) zig = false;
// Moi bo ba chu so lien tiep: chieu tang/giam phai doi chieu
for (size_t i = 1; i + 1 < s.size() && zig; i++) {
bool up1 = s[i - 1] < s[i];
bool up2 = s[i] < s[i + 1];
if (up1 == up2) zig = false;
}
if (zig) cnt++;
}
cout << cnt << "\n";
return 0;
}
Sub 2: Thử chia đến căn bậc hai — ~O(N \cdot \sqrt{a})~
Kiểm tra nguyên tố chỉ cần thử ước d đến d·d ≤ a (vì nếu có ước lớn hơn căn thì sẽ có ước nhỏ hơn căn tương ứng). Phần kiểm tra chữ số tách thành hàm zigzag để dễ đọc. Với a < 10^6, mỗi lần kiểm tra chỉ khoảng 1000 phép chia.
Kết quả chấm: đạt 10/10 test.
#include <bits/stdc++.h>
using namespace std;
// Kiem tra nguyen to bang thu chia den can bac hai (a < 10^6)
bool isPrime(long long a) {
if (a < 2) return false;
for (long long d = 2; d * d <= a; d++)
if (a % d == 0) return false;
return true;
}
// Kiem tra cac chu so luan phien tang giam (it nhat 2 chu so)
bool zigzag(const string &s) {
if (s.size() < 2) return false;
for (size_t i = 0; i + 1 < s.size(); i++)
if (s[i] == s[i + 1]) return false; // hai chu so lien tiep phai khac nhau
for (size_t i = 1; i + 1 < s.size(); i++)
if ((s[i - 1] < s[i]) == (s[i] < s[i + 1])) return false; // chieu phai doi nhau
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("LONGAN.INP", "r")) { freopen("LONGAN.INP", "r", stdin); freopen("LONGAN.OUT", "w", stdout); }
int n;
cin >> n;
int cnt = 0;
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
if (isPrime(a) && zigzag(to_string(a))) cnt++;
}
cout << cnt << "\n";
return 0;
}
Bình luận