Bài 3: Tổng nguyên tố 3 - Tài liệu Tin học

Đăng bởi Admin

Tháng 10 9, 2022

https://chuyenhalong.ucode.vn/problems/tong-nguyen-to-3-119184

Cho dãy số nguyên $x_1, x_2 \ldots, x_N$ và hàm $f(p)$ là số lương các phần tử thuộc dãy $x$ chia hết cho $p$ .
Cho $M$ truy vấn, mỗi truy vấn cho hai số nguyên $l_b, r_i$ . Bạn phải trả lời câu hỏi: Tính tổng: $\sum_{p e s\left(l_i, r_i\right)}^{\square} f(p)$ , ở đây $S\left(l_b r_i\right)$ là tập các số nguyên tố thuộc đoạn $\left[l_b r_l\right]$ .

Đầu vào
– Dòng đầu tiên chứa giá trị $N\left(1 \leq N \leq 10^{\circ}\right)$
– Dòng hai chứa $N$ số nguyên $x_b, x_2, \ldots, x_N\left(2 \leq x_i \leq 10^5\right)$
– Dòng ba chứa giá trị $M\left(1 \leq M \leq 5^* 10^*\right)$
– $M$ dòng tiếp theo, mỗi dòng chứa hai số $l_b r_i\left(2 \leq l_i \leq r_i \leq 2 * 10^{\circ}\right)$

Đầu ra
– Gồm $\mathrm{M}$ dòng, mỗi dòng là câu trả lời của truy vấn tương ứng.

Ràng buộc
– $40 \%$ test $1 \leq N, M \leq 100 ; 1 \leq l_i \leq r_i \leq 1000$
– $40 \%$ test tiếp theo $1 \leq N, M \leq 1000 ; 1 \leq l_i \leq r_i \leq 1000$
– $20 \%$ test còn lại $l \leq N \leq 10^6, 2 \leq x_i \leq 10^5, 1 \leq M \leq 5^* 10^4, 2 \leq l_i \leq r_i \leq 2 * 10^{\circ}$

Ví dụ

Sample input	Sample output
6 5 5 7 10 14 15 3 2 11 3 12 4 4	9 7 0

Giải thích:
– Tại truy vấn $1: l=2, r=11$ :
Ta cần tính $f(2)+f(3)+f(5)+f(7)+f(11)=2+1+4+2+0=0$ .
– Tại try vấn $2: l=3, r=12$ :
Ta cần tính $f(3)+f(5)+f(7)+f(11)=1+4+2+0=7$
Tại truy vấn $3: l=4, r=4$ : không có số nguyên tố nào thuộc đoạn $[l, r]$ , nên kết quả truy vấn bằng 0