Hướng dẫn giải của [200 đề thầy Đức] Bài 98: Số Sphenic
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ố Sphenic là số bằng tích của đúng ba số nguyên tố khác nhau, tức là dạng $p \cdot q \cdot r$ với $p, q, r$ đôi một khác nhau. Cần kiểm tra $N$ có phải dạng đó không: in $1$ nếu đúng, ngược lại in $0$.
Điều kiện cần nhớ: mỗi thừa số nguyên tố phải có số mũ đúng bằng $1$ (ví dụ $60 = 2^2 \cdot 3 \cdot 5$ không phải sphenic), và phải có đúng ba thừa số.
Sub 1: Vét cạn — ~O(N)~, dùng khi ~N \le 1000~
Thử mọi $d$ từ $2$ đến $N$. Mỗi khi $d$ chia hết số còn lại $m$, đếm số mũ $e$ của $d$ trong $N$, tăng số thừa số lên một, và nếu $e > 1$ thì đánh dấu sai. Cuối cùng in $1$ khi có đúng ba thừa số và không có số mũ nào lớn hơn $1$.
Kết quả chấm riêng sub này: đúng 21/21 test.
Sub 2: Thử đến căn bậc hai — ~O(\sqrt{N})~
Giống sub 1, nhưng chỉ thử $d$ với $d \cdot d \le m$. Nếu sau vòng lặp $m > 1$ thì $m$ là một thừa số nguyên tố lớn (số mũ $1$, vì nếu $m$ có số mũ lớn hơn $1$ thì phải có ước $d \le \sqrt{m}$, đã bị loại), và được tính thêm một thừa số.
Bẫy cần chú ý: phần còn lại $m$ đã bị chia nhỏ, nên phải kiểm tra thừa số cuối cùng bằng $m > 1$ chứ không dùng $N$.
Kết quả chấm riêng sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc $T$, rồi với mỗi test đọc $N$. Nếu $N \le 1000$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
long long N;
// Sub 1: vét cạn — thử mọi d từ 2 đến N, đếm số thừa số nguyên tố và kiểm tra mỗi thừa số chỉ xuất hiện một lần
// Dùng khi N <= 10^6
void sub1() {
int cnt = 0; // số thừa số nguyên tố (phân biệt)
bool ok = true; // còn đúng là tích của các số nguyên tố khác nhau không
long long m = N;
for (long long d = 2; d <= m; d++) {
if (m % d == 0) {
int e = 0;
while (m % d == 0) { m /= d; e++; }
cnt++;
if (e > 1) ok = false; // có lũy thừa > 1 thì không phải sphenic
}
}
cout << ((ok && cnt == 3) ? 1 : 0) << "\n";
}
// Sub 2: chỉ thử d đến căn bậc hai của phần còn lại — nhanh hơn sub 1
void sub2() {
int cnt = 0;
bool ok = true;
long long m = N;
for (long long d = 2; d * d <= m; d++) {
if (m % d == 0) {
int e = 0;
while (m % d == 0) { m /= d; e++; }
cnt++;
if (e > 1) ok = false;
}
}
if (m > 1) cnt++; // phần còn lại là một thừa số nguyên tố lớn (lũy thừa 1)
cout << ((ok && cnt == 3) ? 1 : 0) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> N;
if (N <= 1000) sub1(); // N nhỏ: vét cạn cho chắc
else sub2(); // N lớn: chỉ thử đến căn bậc hai
}
return 0;
}
Bình luận