Hướng dẫn giải của Các số có 3 ước (đề KS ĐH 2024)
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
Số có đúng 3 ước nguyên dương là ~p^2~ với ~p~ là số nguyên tố. Cần tách các dãy chữ số lớn nhất trong xâu, kiểm tra từng số có phải bình phương của số nguyên tố.
Sub 1: Thử chia — dùng khi độ dài xâu không vượt quá 1000
Tách các dãy chữ số liên tiếp, bỏ số 0 đứng đầu. Với mỗi số ~v~ có tối đa 18 chữ số: kiểm tra ~v~ là bình phương đúng của ~r~, rồi kiểm tra ~r~ là số nguyên tố bằng cách thử chia đến ~\sqrt{r}~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Sàng nguyên tố đến 31623 — dùng khi độ dài xâu lớn hơn 1000
Giống sub 1 nhưng kiểm tra ~r~ nguyên tố bằng bảng sàng đến 31623 (vì ~r \le 10^9~).
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Quy ước: đề không giới hạn độ dài một số; như mọi lời giải thông thường, ta giả sử mỗi số trong xâu nhỏ hơn ~10^{18}~ (vừa kiểu số nguyên 64 bit; trong các test lớn nhất chỉ có 9 chữ số). Các dãy dài hơn 18 chữ số bị bỏ qua.
#include <bits/stdc++.h>
using namespace std;
string S;
vector<unsigned long long> runs; // cac day so (da bo so 0 dau), dung chung cho cac sub
// Lay cac so nguyen trong S: moi day chu so lien tiep duoc tach rieng.
void collectRuns() {
size_t i = 0, len = S.size();
while (i < len) {
if (!isdigit((unsigned char)S[i])) { i++; continue; }
size_t j = i;
while (j < len && isdigit((unsigned char)S[j])) j++;
string run = S.substr(i, j - i);
i = j;
size_t p = 0;
while (p + 1 < run.size() && run[p] == '0') p++; // bo so 0 dau
string t = run.substr(p);
if (t.size() > 18) continue; // xem ghi chu trong file .md
runs.push_back(t.empty() ? 0ULL : stoull(t));
}
}
// Can bac hai nguyen cua v (chinh xac).
unsigned long long isqrtU(unsigned long long v) {
unsigned long long r = (unsigned long long)sqrtl((long double)v);
while (r * r > v) r--;
while ((r + 1) * (r + 1) <= v) r++;
return r;
}
// Sub 1: vet can. So co dung 3 uoc la p^2 (p nguyen to). Kiem tra p bang chia thu tu 2 den can p.
void sub1() {
long long cnt = 0;
for (unsigned long long v : runs) {
unsigned long long r = isqrtU(v);
if (r < 2 || r * r != v) continue;
bool prime = true;
for (unsigned long long d = 2; d * d <= r; d++)
if (r % d == 0) { prime = false; break; }
if (prime) cnt++;
}
cout << cnt << "\n";
}
// Sub 2: giong sub 1 nhung kiem tra p nguyen to bang sang nguyen to den 31623 (can cua 10^9).
// Do p <= 10^9 nen chi can sang den 31623.
void sub2() {
const int LIM = 31623;
vector<bool> comp(LIM + 1, false);
comp[0] = comp[1] = true;
for (int i = 2; i * i <= LIM; i++)
if (!comp[i])
for (int j = i * i; j <= LIM; j += i) comp[j] = true;
long long cnt = 0;
for (unsigned long long v : runs) {
unsigned long long r = isqrtU(v);
if (r < 2 || r * r != v) continue;
bool prime = true;
for (unsigned long long d = 2; d <= (unsigned long long)LIM && d * d <= r; d++)
if (!comp[d] && r % d == 0) { prime = false; break; }
if (prime) cnt++;
}
cout << cnt << "\n";
}
int main() {
cin >> S;
collectRuns();
// Du lieu nho: sub 1. Du lieu lon: sub 2.
if (S.size() <= 1000) sub1();
else sub2();
return 0;
}
Bình luận