Số nguyên tố (PRIME)
Đề bài
Kì thi chọn đội dự tuyển Tin học Trường THPT chuyên Hà Nội - Amsterdam năm học 2022-2023
PRIME – Số nguyên tố
Fuy học lớp 12 toán 1 và cậu rất yêu thích các con số nguyên tố. Fuy muốn đưa ra một thử thách như sau:
Cho ba số nguyên dương $l, r, val$. Với mỗi số nguyên dương $x$, ta quy định $f(x)$ như sau:
$$f(x) = \begin{cases} |val - x|, & \text{nếu } x \text{ là số nguyên tố} \\ 0, & \text{nếu } x \text{ không phải số nguyên tố} \end{cases}$$
Hãy tính tổng mọi $f(x)$ với $l \le x \le r$.
Bạn phải trả lời $q$ truy vấn như vậy.
Dữ liệu:
- Dòng đầu chứa số nguyên dương $q$ $(1 \le q \le 10^5)$.
- $q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương $l, r, val$ $(l \le r \le 10^5,\ val \le 10^9)$.
Kết quả:
- In ra $q$ dòng, dòng thứ $i$ chứa kết quả của truy vấn thứ $i$.
Chấm điểm:
- Subtask 1 (20% số test): $q, l, r \le 100$.
- Subtask 2 (30% số test): $q, l, r \le 10^4$.
- Subtask 3 (30% số test): Trong mỗi truy vấn: $val \le l$ hoặc $val \ge r$.
- Subtask 4 (20% số test): Không có ràng buộc gì thêm.
1
4 10 62Giải thích: $|6 - 5| + |6 - 7| = 2$.
Lời mở đầu
Bài này mình được một em học viên hỏi: "Anh xem hộ em bài 3 ạ. Em dùng sàng ăn được 50%". Mình đã AC và hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJGiải thích ví dụ cho bạn nào chưa hiểu đề: với $l = 4, r = 10, val = 6$, các số $x$ từ $4$ đến $10$ là $4, 5, 6, 7, 8, 9, 10$. Chỉ có $5$ và $7$ là số nguyên tố nên chỉ hai số này đóng góp $|6 - 5| = 1$ và $|6 - 7| = 1$; các số còn lại có $f(x) = 0$. Tổng là 2.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Cách 1Sàng nguyên tố + duyệt từng số trong đoạn – O(N log log N + q · N)
Vì $l, r \le 10^5$ nên chắc chắn phải dùng sàng nguyên tố Eratosthenes, sàng từ $1$ đến $10^5$ để khi cần kiểm tra một số bất kỳ trong đoạn đó có phải số nguyên tố không thì biết ngay trong $O(1)$. Việc sàng chỉ tốn $O(N \log \log N)$ với $N = 10^5$ nên không sợ TLE. Về sàng nguyên tố thì bạn nào chưa rõ có thể tham khảo bài viết này trên VNOI: Lý thuyết số – VNOI Wiki.
Sàng xong thì làm đúng theo đề: với mỗi truy vấn, cho $x$ chạy từ $l$ đến $r$, vị trí nào là số nguyên tố thì cộng $|val - x|$ vào kết quả, không phải thì coi như cộng $0$ (bỏ qua). Đây chính là cách mà em học viên đã làm.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
bool isPrime[N + 1];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
for(int i = 0; i <= N; ++i){
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for(int i = 2; i * i <= N; ++i){
if(isPrime[i] == true){
for(int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
int q;
cin >> q;
while(q--){
long long l, r, val;
cin >> l >> r >> val;
long long res = 0;
for(long long x = l; x <= r; ++x){
if(isPrime[x]){
res += abs(val - x);
}
}
cout << res << '\n';
}
return 0;
}import sys
def main():
N = 100000
is_prime = bytearray([1]) * (N + 1)
is_prime[0] = 0
is_prime[1] = 0
i = 2
while i * i <= N:
if is_prime[i]:
is_prime[i * i::i] = bytes(len(range(i * i, N + 1, i)))
i += 1
data = sys.stdin.buffer.read().split()
q = int(data[0])
out = []
pos = 1
for _ in range(q):
l, r, val = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
res = 0
for x in range(l, r + 1):
if is_prime[x]:
res += abs(val - x)
out.append(res)
print("\n".join(map(str, out)))
main()Đánh giá độ phức tạp của cách làm này:
- Không gian: $O(N)$ cho mảng sàng.
- Thời gian: sàng $O(N \log \log N)$, mỗi truy vấn duyệt tối đa $r - l + 1 \le 10^5$ số ⇒ tổng $O(q \cdot N)$, xấu nhất là $10^5 \cdot 10^5 = 10^{10}$ phép tính.
long long nhé.Cách 2Tách 2 nhóm quanh val + prefixSum, prefixCount – O(N log log N + q)
Đầu tiên, các vị trí không phải số nguyên tố đóng góp $0$, nên nói cách khác ta chỉ quan tâm đến các số nguyên tố trong đoạn $[l, r]$. Sau khi sàng xong, các bạn phải đưa ra được nhận xét như sau.
Ví dụ $l = 4, r = 20$. Các số nguyên tố trong đoạn này là: $5, 7, 11, 13, 17, 19$. Giả sử $val = 12$. Ta tìm số nguyên tố lớn nhất trong danh sách mà $\le val$, chính là $11$. Vậy tách ra 2 nhóm:
- Nhóm trái $\{5, 7, 11\}$ (đều $\le val$): mỗi $|val - x| = val - x$. Tổng $5 + 7 + 11 = 23$, có $3$ số ⇒ đóng góp $val \cdot 3 - 23 = 36 - 23 = 13$. Kiểm tra: $|5 - 12| + |7 - 12| + |11 - 12| = 7 + 5 + 1 = 13$ ✅.
- Nhóm phải $\{13, 17, 19\}$ (đều $\gt val$): mỗi $|val - x| = x - val$. Tổng $13 + 17 + 19 = 49$, có $3$ số ⇒ đóng góp $49 - val \cdot 3 = 49 - 36 = 13$. Kiểm tra: $1 + 5 + 7 = 13$ ✅.
Cộng lại: $13 + 13 = 26$ là kết quả. Hai trường hợp đặc biệt:
- $val = 4$: toàn bộ danh sách đều $\ge val$ ⇒ đáp án $= (5 + 7 + 11 + 13 + 17 + 19) - val \cdot 6 = 72 - 24 = 48$. Thử tính: $1 + 3 + 7 + 9 + 13 + 15 = 48$ ✅.
- $val = 30$: toàn bộ danh sách đều $\le val$ ⇒ đáp án $= val \cdot 6 - 72 = 180 - 72 = 108$. Thử tính: $25 + 23 + 19 + 17 + 13 + 11 = 108$ ✅.
- Nhóm toàn số $\le val$: $\sum |val - x| = val \cdot c - s$.
- Nhóm toàn số $\ge val$: $\sum |val - x| = s - val \cdot c$.
Việc còn lại là làm sao để mỗi truy vấn đều ra kết quả ngay trong $O(1)$. Mình cần 5 mảng:
isPrime[i]: mảng sàng.prefixSum[i]: tổng các số nguyên tố $\le i$. Ví dụ tổng các số nguyên tố từ $7$ đến $13$ là $7 + 11 + 13 = 31$ =prefixSum[13] - prefixSum[6].prefixCount[i]: số lượng số nguyên tố $\le i$. Ví dụ từ $3$ đến $11$ có $4$ số nguyên tố ($3, 5, 7, 11$) =prefixCount[11] - prefixCount[2].left[i]: số nguyên tố lớn nhất $\le i$ (mảng trung gian).right[i]: số nguyên tố nhỏ nhất $\ge i$ (mảng trung gian).
Với cận $l, r$, ta xác định ngay trong $O(1)$ danh sách số nguyên tố bắt đầu từ số nào và kết thúc ở số nào: start = right[l], finish = left[r]. Ví dụ $l = 4, r = 20$ thì start = 5, finish = 19. Rồi với $val$ sẽ có 3 trường hợp:
- $val \lt start$: cả danh sách đều lớn hơn $val$ ⇒ đáp án $= S(start, finish) - val \cdot C(start, finish)$.
- $val \gt finish$: cả danh sách đều nhỏ hơn $val$ ⇒ đáp án $= val \cdot C(start, finish) - S(start, finish)$.
- $start \le val \le finish$: lấy
mid = left[val](số nguyên tố lớn nhất $\le val$), tách thành nhóm $[start, mid]$ và nhóm $(mid, finish]$ rồi áp hai công thức trên cho từng nhóm và cộng lại.
Trong đó $S(a, b) = $ prefixSum[b] - prefixSum[a - 1] và $C(a, b) = $ prefixCount[b] - prefixCount[a - 1]. Chỗ này các bạn phải chịu khó nháp kỹ chút nhé 😉.
start > finish, nhưng giữa finish và start - 1 không có số nguyên tố nào nên prefixSum[finish] - prefixSum[start - 1] = 0 và tương tự cho prefixCount ⇒ đáp án tự động bằng $0$, không cần xử lý riêng. Ví dụ $l = 24, r = 28$: start = 29, finish = 23, mà prefixSum[23] = prefixSum[28].Minh hoạ một truy vấn
Các bạn nhập $l, r, val$ rồi bấm Tiếp để xem cách xác định start, finish, mid và tính đáp án bằng công thức (xanh dương = nhóm trái $\le val$, xanh lá = nhóm phải $\gt val$, viền cam = vị trí $val$):
Source code để các bạn tham khảo nếu làm theo hướng này (đây là code mình đã AC, mình code hơi vội nên chưa thật sự clean, các bạn đối chiếu với ý tưởng ở trên để hiểu rõ hơn rồi có thể tối ưu thêm nhé):
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N = 100002;
bool isPrime[N+1];
for(int i = 0; i <= N; ++i){
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
int left[N+1], prefixSum[N+1], prefixCount[N+1];
prefixSum[0] = prefixSum[1] = 0;
prefixCount[0] = prefixCount[1] = 0;
left[0] = left[1] = 0;
int lastPrime = 0;
for(int i = 2; i * i <= N; ++i){
if(isPrime[i] == true){
for(int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
for(int i = 2; i <= N; ++i){
prefixSum[i] = prefixSum[i - 1];
prefixCount[i] = prefixCount[i - 1];
if(isPrime[i]){
lastPrime = i;
prefixSum[i] += i;
prefixCount[i]++;
}
left[i] = lastPrime;
}
int right[N+1];
lastPrime = 100003;
for(int i = N; i >= 0; --i){
if(isPrime[i]){
lastPrime = i;
}
right[i] = lastPrime;
}
int q;
cin >> q;
while(q--){
long long l, r, val;
cin >> l >> r >> val;
int start = right[l];
int finish = left[r];
if(val < start){
cout << (prefixSum[finish] - prefixSum[start - 1]) - (val * (prefixCount[finish] - prefixCount[start - 1]));
}
else if(val > finish){
cout << (val * (prefixCount[finish] - prefixCount[start - 1])) - (prefixSum[finish] - prefixSum[start - 1]);
}
else{
int mid = left[val];
long long sum1 = (val * (prefixCount[mid] - prefixCount[start - 1])) - (prefixSum[mid] - prefixSum[start - 1]);
long long sum2 = ((prefixSum[finish] - prefixSum[mid]) - (val * (prefixCount[finish] - prefixCount[mid])));
cout << sum1 + sum2;
}
cout << '\n';
}
return 0;
}import sys
def main():
N = 100002
is_prime = bytearray([1]) * (N + 1)
is_prime[0] = 0
is_prime[1] = 0
i = 2
while i * i <= N:
if is_prime[i]:
is_prime[i * i::i] = bytes(len(range(i * i, N + 1, i)))
i += 1
left = [0] * (N + 1) # left[i] = số nguyên tố lớn nhất <= i (0 nếu không có)
prefix_sum = [0] * (N + 1) # tổng các số nguyên tố <= i
prefix_count = [0] * (N + 1) # số lượng số nguyên tố <= i
last_prime = 0
for i in range(2, N + 1):
prefix_sum[i] = prefix_sum[i - 1]
prefix_count[i] = prefix_count[i - 1]
if is_prime[i]:
last_prime = i
prefix_sum[i] += i
prefix_count[i] += 1
left[i] = last_prime
right = [0] * (N + 1) # right[i] = số nguyên tố nhỏ nhất >= i
last_prime = 100003
for i in range(N, -1, -1):
if is_prime[i]:
last_prime = i
right[i] = last_prime
data = sys.stdin.buffer.read().split()
q = int(data[0])
out = []
pos = 1
for _ in range(q):
l, r, val = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
start = right[l]
finish = left[r]
if val < start:
ans = (prefix_sum[finish] - prefix_sum[start - 1]) - val * (prefix_count[finish] - prefix_count[start - 1])
elif val > finish:
ans = val * (prefix_count[finish] - prefix_count[start - 1]) - (prefix_sum[finish] - prefix_sum[start - 1])
else:
mid = left[val]
sum1 = val * (prefix_count[mid] - prefix_count[start - 1]) - (prefix_sum[mid] - prefix_sum[start - 1])
sum2 = (prefix_sum[finish] - prefix_sum[mid]) - val * (prefix_count[finish] - prefix_count[mid])
ans = sum1 + sum2
out.append(ans)
print("\n".join(map(str, out)))
main()left[i], right[i] với $i \ge 2$, nên nếu truy vấn có $l = 1$ (hoặc $r = 1$) thì sẽ đọc phải ô chưa gán giá trị (right[1]) và có thể truy cập prefixSum[-1]. Trong code ở trên mình đã thêm dòng left[0] = left[1] = 0; và cho vòng lặp tính right chạy tới $i = 0$ để an toàn với mọi test.Các bạn bấm chạy tay để xem từng dòng. Các vòng lặp tới $N = 100002$ mình chỉ cho xem chi tiết vài bước đầu, phần còn lại gom thành một bước; bảng dữ liệu hiển thị các ô từ $0$ đến $30$:
Đánh giá độ phức tạp của cách làm này:
- Không gian: 5 mảng kích thước $N \approx 10^5$ ⇒ $O(N)$.
- Thời gian: bước sàng $O(N \log \log N)$ với $N = 10^5$; vài bước tiền xử lý mảng cộng dồn và
left,rightmất $O(N)$; sau cùng là đọc qua $q$ truy vấn, mỗi truy vấn chỉ $O(1)$. Vì $q$ và $N$ đều tối đa $10^5$ nên độ phức tạp căn theo cái lớn nhất chính là bước sàng $O(N \log \log N)$.
val tới $10^9$ nhân với số lượng số nguyên tố (tới $9592$) sẽ vượt int, nên l, r, val và sum1, sum2 phải là long long. Còn prefixSum thì tổng các số nguyên tố $\le 10^5$ chỉ khoảng $4.5 \cdot 10^8$ nên int vẫn đủ.- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét