Nộp bài
Điểm:
1600 (thành phần)
Thời gian:
1.5s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Cho mảng a gồm n phần tử, mảng b gồm m phần tử. Cho q truy vấn, mỗi truy vấn gồm 4 số (l,r,u,v). Nhiệm vụ của bạn là với mỗi truy vấn, tính tổng của tất cả các cặp ước chung lớn nhất của a_i và b_j với mọi l \le i \le r và u \le j \le v. Hay nói cách khác, tính:
\sum^{i=l}_{i \le r} \sum^{j = u}_{j \le v}gcd(a_i,b_j)
Input, Output và Subtasks
Input: (bàn phím
)
- Dòng đầu chứa 2 số nguyên dương n,m (1 \le n,m \le 10^5).
- Dòng tiếp theo chứa a_1,a_2,...,a_n (1 \le a_i \le 10^3).
- Dòng tiếp theo chứa b_1,b_2,...,b_m (1 \le b_j \le 10^3).
- Dòng tiếp theo chứa số nguyên dương q (1 \le q \le 10^4).
- q dòng tiếp theo, mỗi dòng chứa 4 số nguyên dương l,r,u,v (1 \le l \le r \le n, 1 \le u \le v \le m).
Output: (màn hình
)
- Với mỗi truy vấn in ra kết quả cần tìm.
Subtasks
- Subtask 1 (10 \%) n,m,q \le 100.
- Subtask 2 (20 \%) n,m \le 1000.
- Subtask 3 (30 \%) a_i,b_j\le 100.
- Subtask 4 (40 \%) không có giới hạn gì thêm
Sample
Input (bàn phím
)
2 4
2 5
4 10 6 11
2
1 2 1 3
1 2 2 4
Output (màn hình
)
13
12
Bình luận