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

View as PDF

Submit solution

Points: 1600 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type

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_ib_j với mọi l \le i \le ru \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

Comments

There are no comments at the moment.