Hướng dẫn giải của [200 đề thầy Đức] Bài 97: Số Smith
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ố Smith là hợp số $n$ mà tổng chữ số của $n$ bằng tổng các chữ số của các thừa số nguyên tố trong phân tích $n$ (kể cả thừa số lặp). Cần in $1$ nếu $n$ là số Smith, ngược lại in $0$.
Lưu ý các trường hợp đặc biệt: số nguyên tố có đúng một thừa số (chính nó) nên phải loại ra, và số $1$ không có thừa số nào nên cũng không phải số Smith.
Sub 1: Vét cạn — ~O(n)~, dùng khi ~n \le 10^6~
Thử mọi $d$ từ $2$ đến $n$, mỗi khi $d$ chia hết số còn lại $m$ thì cộng tổng chữ số của $d$ vào tổng và đếm thêm một thừa số, rồi chia $m$ cho $d$. Cuối cùng so sánh tổng chữ số của $n$ với tổng này, và kiểm tra số thừa số ít nhất là $2$.
Kết quả chấm riêng sub này: đúng 11/21 test (các test còn lại quá giờ vì $n$ lớn hơn miền của sub).
Sub 2: Thử đến căn bậc hai — ~O(\sqrt{n})~, dùng cho ~n \le 10^9~
Giống sub 1, nhưng chỉ thử $d$ với $d \cdot d \le m$. Sau vòng lặp, nếu $m > 1$ thì $m$ là một thừa số nguyên tố lớn và được cộng vào tổng như một thừa số bình thường.
Bẫy cần chú ý: tổng chữ số của $n$ tối đa khoảng $81$ nên có thể dùng long long mà không lo tràn, nhưng phải tính tổng chữ số của $m$ sau khi chia xong, không phải của $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 10^6$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
long long n;
// Tổng các chữ số của x
long long digitSum(long long x) {
long long s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: vét cạn — thử mọi d từ 2 đến n để tìm thừa số nguyên tố
// Dùng khi n <= 10^6
void sub1() {
long long sumFactors = 0; // tổng chữ số các thừa số nguyên tố
int cnt = 0; // số thừa số nguyên tố (kể cả lặp)
long long m = n;
for (long long d = 2; d <= m; d++)
while (m % d == 0) { sumFactors += digitSum(d); cnt++; m /= d; }
// Số nguyên tố (cnt == 1) hoặc số 1 (cnt == 0) không phải số Smith
if (cnt >= 2 && digitSum(n) == sumFactors) cout << 1 << "\n";
else cout << 0 << "\n";
}
// Sub 2: chỉ thử d đến căn bậc hai — dùng cho n lớn (đến 10^9)
// Phần m còn lại sau vòng lặp (nếu > 1) là một thừa số nguyên tố lớn
void sub2() {
long long sumFactors = 0;
int cnt = 0;
long long m = n;
for (long long d = 2; d * d <= m; d++)
while (m % d == 0) { sumFactors += digitSum(d); cnt++; m /= d; }
if (m > 1) { sumFactors += digitSum(m); cnt++; }
if (cnt >= 2 && digitSum(n) == sumFactors) cout << 1 << "\n";
else cout << 0 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
if (n <= 1000000) 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