TLEOJ Contest #15 - Truy vấn tổng GCD

Đ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ả:

Shirokito

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)

Output (màn hình)

13
12

Bình luận

Không có bình luận nào.