Hướng dẫn giải của Đếm 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ố nguyên dương trong [1, N] (N ≤ 10^5) có tổng chữ số là số nguyên tố. Tổng chữ số lớn nhất chỉ là 45 (số 99999) nên có thể kiểm tra nguyên tố rất nhanh.
Sub 1: Vét cạn — ~O(N \log N)~
Với mỗi số i từ 1 đến N, tách từng chữ số để tính tổng, rồi kiểm tra tổng đó có phải số nguyên tố bằng cách thử mọi ước. Cách này đúng với mọi test.
Kết quả chấm: 20/20 (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
// Kiem tra nguyen to bang cach thu moi uoc
bool laNguyenTo(int x) {
if (x < 2) return false;
for (int d = 2; d < x; d++)
if (x % d == 0) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
long long n;
cin >> n;
long long dem = 0;
// Vet can: voi moi so i, tinh tong chu so roi kiem tra nguyen to
for (long long i = 1; i <= n; i++) {
long long x = i;
int tong = 0;
while (x > 0) {
tong += x % 10;
x /= 10;
}
if (laNguyenTo(tong)) dem++;
}
cout << dem << "\n";
return 0;
}
Sub 2: Tính tổng chữ số nhanh, bảng nguyên tố — ~O(N)~
Thay vì tính lại tổng chữ số cho mỗi số, dùng công thức truy hồi ds[i] = ds[i / 10] + i % 10 (số i có tổng chữ số bằng tổng chữ số của i / 10 cộng chữ số cuối). Tính trước bảng nguyên tố cho các tổng từ 0 đến 50 nên mỗi số chỉ cần tra bảng O(1).
Bẫy: đây là bài dễ nên cả hai sub đều đạt đủ điểm; sub 2 chỉ là cách viết gọn và nhanh hơn.
Kết quả chấm: 20/20
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int n;
cin >> n;
// Tong chu so cua so <= 10^5 khong vuot qua 45 (so 99999)
const int MAX_S = 50;
bool laNT[MAX_S + 1];
for (int s = 0; s <= MAX_S; s++) {
laNT[s] = (s >= 2);
for (int d = 2; d * d <= s; d++)
if (s % d == 0) { laNT[s] = false; break; }
}
// ds[i] = tong chu so cua i, tinh nhanh: ds[i] = ds[i / 10] + i % 10
vector<int> ds(n + 1, 0);
long long dem = 0;
for (int i = 1; i <= n; i++) {
ds[i] = ds[i / 10] + i % 10;
if (laNT[ds[i]]) dem++;
}
cout << dem << "\n";
return 0;
}
Bình luận