Hướng dẫn giải của TMP2526_CAU2
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 tố trong đoạn ~[L, R]~ có tổng chữ số chia hết cho ~K~, với ~R \le 10^7~. Với đoạn nhỏ thì kiểm tra từng số bằng chia thử; với đoạn lớn thì dùng sàng.
Sub 1: Vét cạn — ~O((R - L) \sqrt{R})~, dùng khi ~R \le 10^5~
Với mỗi ~x~ trong đoạn, kiểm tra nguyên tố bằng chia thử đến căn bậc hai, tính tổng chữ số và kiểm tra chia hết cho ~K~. Nếu chỉ nộp sub này: đúng 17/27 test.
Sub 2: Sàng nguyên tố — ~O(R \log \log R)~
Sàng đến ~R~ một lần rồi duyệt đoạn ~[L, R]~, mỗi số kiểm tra tổng chữ số. Nếu chỉ nộp sub này: đúng 27/27 test.
Chương trình hoàn chỉnh
~main~ đọc ~L, R, K~. Nếu ~R \le 10^5~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
long long L, R, K;
bool isPrime(long long x) {
if (x < 2) return false;
for (long long d = 2; d * d <= x; d++)
if (x % d == 0) return false;
return true;
}
long long digitSum(long long x) {
long long s = 0;
while (x > 0) { s += x % 10; x /= 10; }
return s;
}
// Sub 1: vet can. Voi moi x trong [L,R], kiem tra nguyen to bang chia thu va tong chu so.
// Dung khi R <= 100000.
void sub1() {
long long cnt = 0;
for (long long x = L; x <= R; x++)
if (isPrime(x) && digitSum(x) % K == 0) cnt++;
cout << cnt << "\n";
}
// Sub 2: sang nguyen to mot lan toi R, roi duyet [L,R]. O(R log log R).
void sub2() {
vector<bool> comp(R + 1, false);
comp[0] = comp[1] = true;
for (long long i = 2; i * i <= R; i++)
if (!comp[i])
for (long long j = i * i; j <= R; j += i) comp[j] = true;
long long cnt = 0;
for (long long x = L; x <= R; x++)
if (!comp[x] && digitSum(x) % K == 0) cnt++;
cout << cnt << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> L >> R >> K;
if (R <= 100000) sub1();
else sub2();
return 0;
}
Bình luận