Tommy (Bài 1 Chọn ĐT HSG Tỉnh THPT chuyên Lê Quý Đôn Vũng Tàu 2025)
Xem PDFChú gấu Tommy là một chú gấu rất dễ thương. Một ngày nọ chú đến trường và được thầy dạy về những con số nguyên tố. Chú và các bạn vô cùng thích thú và lao vào tìm hiểu chúng. Thế nhưng, càng tìm hiểu sâu chú lại càng gặp phải những bài toán khó về số nguyên tố. Hôm nay thầy giao cho cả lớp một bài toán khó và yêu cầu cả lớp làm nhanh nhất để thưởng cho lớp hộp bánh. Vì thế, để có bánh ăn, Tommy phải giải bài toán nhanh nhất có thể. Bài toán như sau:
Cho dãy \(n\) số nguyên dương \(X_1, X_2, \dots, X_n\) và \(m\) truy vấn, mỗi truy vấn được cho bởi \(2\) số nguyên \(L_i, R_i\).
Cho một hàm \(\operatorname{f}(p)\) trả về số lượng các số \(X_i\) là bội của \(p\).
Câu trả lời cho truy vấn \(L_i, R_i\) là tổng \(\sum_{p \in \operatorname{S} \left(L_i, R_i \right)}^{\operatorname{f} \left( p \right)}\), trong đó \(\operatorname{S}(L_i, R_i)\) là tập các số nguyên tố trong đoạn \(\left[ L_i , R_i \right]\).
Yêu cầu: Bạn hãy giúp chú gấu Tommy giải bài toán này nhé!
- Subtask \(1\): \(30\%\) số test có \(0 \lt n, m \le 2 \cdot 10^3, 2 \le L_i ≤ R_i \le 10^3\);
- Subtask \(2\): \(30\%\) số test có \(0 \lt n, m \le 2 \cdot 10^3, 2 \le L_i ≤ R_i \le 10^6\);
- Subtask \(3\): \(40\%\) số test không có ràng buộc gì thêm.
Input
Dữ liệu nhập vào từ file TOMMY.INP:
- Dòng đầu tiên chứa số nguyên \(n\) \(\left( 1 \le n \le 10^5 \right)\).
- Dòng thứ hai chứa \(n\) số nguyên \(X_1, X_2, \dots, X_n\) \(\left( 2 \le X_i \le 10^7 \right)\).
- Dòng thứ ba chứa số nguyên \(m\) \(\left( 1 \le m \le 50000 \right)\).
- Mỗi dòng \(i\) trong \(m\) dòng sau chứa \(2\) số nguyên ngăn cách bởi \(1\) dấu cách \(L_i, R_i\) \(\left( 2 \le L_i \le R_i \le 2 \cdot 10^9 \right)\).
Output
Kết quả ghi vào file TOMMY.OUT gồm \(m\) dòng, mỗi dòng chứa \(1\) số nguyên là câu trả lời cho \(1\) truy vấn.
Example
Test 1
Input
6
5 5 7 10 14 15
3
2 11
3 12
4 4
Output
9
7
0
Note
-
Truy vấn \(1\): \(L_1 = 2, R_1 = 11\).
Ta cần tính: \(\operatorname{f}(2) + \operatorname{f}(3) + \operatorname{f}(5) + \operatorname{f}(7) + \operatorname{f}(11) = 2 + 1 + 4 + 2 + 0 = 9\). -
Truy vấn \(2\): \(L_2 = 3, R_2 = 12\).
Ta cần tính: \(\operatorname{f}(3) + \operatorname{f}(5) + \operatorname{f}(7) + \operatorname{f}(11) = 1 + 4 + 2 + 0 = 7\). -
Truy vấn \(3\): \(L_3 = 4, R_3 = 4\)
\(\rightarrow\) Không có số nguyên tố.
Bình luận
Tommy (Bài 1 Chọn ĐT HSG Tỉnh THPT chuyên Lê Quý Đôn Vũng Tàu 2025)
Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
DigiEnceladus
Dạng bài
Điểm:100 (p)
Thời gian:1.0s
Bộ nhớ:256M
Input:TOMMY.INP
Output:TOMMY.OUT
Chú gấu Tommy là một chú gấu rất dễ thương. Một ngày nọ chú đến trường và được thầy dạy về những con số nguyên tố. Chú và các bạn vô cùng thích thú và lao vào tìm hiểu chúng. Thế nhưng, càng tìm hiểu sâu chú lại càng gặp phải những bài toán khó về số nguyên tố. Hôm nay thầy giao cho cả lớp một bài toán khó và yêu cầu cả lớp làm nhanh nhất để thưởng cho lớp hộp bánh. Vì thế, để có bánh ăn, Tommy phải giải bài toán nhanh nhất có thể. Bài toán như sau:
Cho dãy
n
n số nguyên dương
X
1
,
X
2
,
…
,
X
n
X
1
,X
2
,…,X
n
và
m
m truy vấn, mỗi truy vấn được cho bởi
2
2 số nguyên
L
i
,
R
i
L
i
,R
i
.
Cho một hàm
f
(
p
)
f(p) trả về số lượng các số
X
i
X
i
là bội của
p
p.
Câu trả lời cho truy vấn
L
i
,
R
i
L
i
,R
i
là tổng
∑
p
∈
S
(
L
i
,
R
i
)
f
(
p
)
∑
p∈S(L
i
,R
i
)
f(p)
, trong đó
S
(
L
i
,
R
i
)
S(L
i
,R
i
) là tập các số nguyên tố trong đoạn
[
L
i
,
R
i
]
[L
i
,R
i
].
Yêu cầu: Bạn hãy giúp chú gấu Tommy giải bài toán này nhé!
Subtask
1
1:
30
%
30% số test có
0
<
n
,
m
≤
2
⋅
1
0
3
,
2
≤
L
i
≤
R
i
≤
1
0
3
0<n,m≤2⋅10
3
,2≤L
i
≤R
i
≤10
3
;
Subtask
2
2:
30
%
30% số test có
0
<
n
,
m
≤
2
⋅
1
0
3
,
2
≤
L
i
≤
R
i
≤
1
0
6
0<n,m≤2⋅10
3
,2≤L
i
≤R
i
≤10
6
;
Subtask
3
3:
40
%
40% số test không có ràng buộc gì thêm.
Input
Dữ liệu nhập vào từ file TOMMY.INP:
Dòng đầu tiên chứa số nguyên
n
n
(
1
≤
n
≤
1
0
5
)
(1≤n≤10
5
).
Dòng thứ hai chứa
n
n số nguyên
X
1
,
X
2
,
…
,
X
n
X
1
,X
2
,…,X
n
(
2
≤
X
i
≤
1
0
7
)
(2≤X
i
≤10
7
).
Dòng thứ ba chứa số nguyên
m
m
(
1
≤
m
≤
50000
)
(1≤m≤50000).
Mỗi dòng
i
i trong
m
m dòng sau chứa
2
2 số nguyên ngăn cách bởi
1
1 dấu cách
L
i
,
R
i
L
i
,R
i
(
2
≤
L
i
≤
R
i
≤
2
⋅
1
0
9
)
(2≤L
i
≤R
i
≤2⋅10
9
).
Output
Kết quả ghi vào file TOMMY.OUT gồm
m
m dòng, mỗi dòng chứa
1
1 số nguyên là câu trả lời cho
1
1 truy vấn.
Example
Test 1
Input
Output
Note
0
Thích
Bình luận
(1)
Lưu
Chia sẻ
Báo cáo
Bình luận
duyyhhhhh
•
2 ngày trước
•
bài y chang hồi tôi làm contest 1 của duyên hải luôn+)))
0
Phản hồi
Chia sẻ
Bài tập gợi ý:
T-prime 3
DSA03005
DSA03004
Bảng số
Hành Trình Không Dừng
Candies
LQDOJ Contest #15 - Bài 1 - Gói bánh chưng
LQDOJ Contest #15 - Bài 2 - Bàn tiệc
proudly powered by DMOJ| developed by LQDJudge team
Tiếng Việt (vi)
bài y chang hồi tôi làm contest 1 của duyên hải luôn+)))