Chọn Đội tuyển HSGQG Quảng Trị 2024 - GCDS
Xem dạng PDF
Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử. Việt Anh định nghĩa hàm ~f(i, j)~ là tổng của tất cả giá trị ~\frac{a_i \times a_j}{d^2}~ với ~d~ là một ước chung của ~a_i~ và ~a_j~. Ước chung của hai số nguyên dương ~x, y~ là số tự nhiên ~d~ mà ~x, y~ đều chia hết cho ~d~.
Ví dụ dãy ~A = \{2, 1, 4\}~ thì ~f(1, 3) = (2 \times 4)/1^2 + (2 \times 4)/2^2 = 10~ với ~\{1, 2\}~ là các ước chung của 2 và 4, ~f(1, 2) = (2 \times 1)/1^2 = 2~ và ~f(2, 3) = (1 \times 4)/1^2 = 4~.
Tổng GCDS của dãy số chính là tổng tất cả các ~f(i, j)~ định nghĩa ở trên sao cho ~1 \leq i < j \leq N~. Dãy ~A = \{2, 1, 4\}~ có tổng GCDS là ~f(1, 2) + f(1, 3) + f(2, 3) = 16~.
Việt Anh biết các bạn trường THPT Chuyên Lê Quý Đôn học lập trình rất tốt nên đưa ra bài toán như sau: Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử cần tính tổng GCDS của dãy số. Ngoài ra, Việt Anh còn thực hiện thêm ~Q~ truy vấn, với mỗi truy vấn cho hai số ~(x, y)~ gán phần tử ~a_x = y~. Hãy tính tổng GCDS của dãy số mới.
Yêu cầu: Cho dãy số nguyên dương ~a_1, a_2, \ldots, a_N~ có ~N~ phần tử, thực hiện:
Tính tổng GCDS của dãy số ban đầu;
Trả lời ~Q~ truy vấn, với mỗi truy vấn ~(x, y)~ hãy tính tổng GCDS của dãy số sau khi cập nhật ~a_x = y~.
Input
Dữ liệu vào từ tệp văn bản GCDS.INP có cấu trúc sau:
Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ (~1 \leq N, Q \leq 5 \times 10^5~);
Dòng thứ 2 ghi dãy ~a_1, a_2, \ldots, a_N~ (~1 \leq a_i \leq 5 \times 10^5~);
~Q~ dòng tiếp theo, mỗi dòng ghi hai số ~x~ và ~y~ biểu thị truy vấn gán ~a_x = y~ (~1 \leq x \leq N~, ~1 \leq y \leq 5 \times 10^5~).
Output
Kết quả ghi ra tệp văn bản GCDS.OUT gồm:
Dòng đầu tiên ghi phần dư của tổng GCDS của dãy số ban đầu khi chia ~10^9 + 7~;
~Q~ dòng tiếp theo, mỗi dòng ghi một số là phần dư của tổng GCDS của dãy khi chia ~10^9 + 7~ tương ứng với thứ tự truy vấn trong tệp dữ liệu vào.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~N, Q, a_x, y \le 100~ |
| 2 | ~30\%~ | ~N, Q \le 100~ |
| 3 | ~10\%~ | ~a_x, y \le 12~ |
| 4 | ~20\%~ | ~a_x~ và ~y~ là số nguyên tố |
| 5 | ~20\%~ | Không có ràng buộc nào thêm. |
Sample Input 1
2 2
2 4
1 4
1 3
Sample Output 1
10
21
12
Sample Input 2
4 3
462955 253652 126897 278176
2 5432
1 2314
3 2
Sample Output 2
57273948
41211035
109845881
827916911
Bình luận
Spoil ⚠️