Lại là tính tổng! Cô giáo yêu cầu Thắng phải hoàn thành một bài toán về tính tổng, nhưng do nghỉ phòng chống dịch Covid-19 thời gian dài, Thắng quên kiến thức về lĩnh vực này nên đành nhờ đến tài năng của các bạn với bài toán như sau:

Yêu cầu:

Cho số nguyên dương N ~(N ≤ 10^5)~. Tính tổng ~S(N) = 1^2 + 2^2 +…+ N^2~

Dữ liệu:

• Dòng đầu chứa số nguyên dương T là số lượng test ~(T ≤ 10^5)~
• T dòng tiếp theo, mỗi dòng là một số nguyên dương N.

Kết quả:

Ghi T dòng, với mỗi dòng là giá trị tổng S(N) tương ứng.

Ví dụ:

Giải thích:

T = 2 (có 2 test):

• Test 1: ~N = 3, S(3) = 1^2 + 2^2 + 3^2 = 14~
• Test 2: ~N = 14, S(14) = 1^2 + 2^2 + … + 14^2 = 1015~

Ràng buộc:

• Có 80% số điểm ứng với ~1 ≤ N, T ≤ 10^3~.
• 20% số test với ~10^3 < N, T ≤ 10^5~

Lợi rất hào hứng với các bài toán số học, lần này Lợi muốn thử năng lực lập trình của các bạn với bài toán như sau: Cho bốn số nguyên dương a, b, x, y ~(a ≤ b; a, b, x, y ≤ 10^9)~.

Yêu cầu:

Đếm số lượng số nguyên dương thuộc đoạn [a ; b] chia hết cho x hoặc chia hết cho y.

Dữ liệu:

Gồm một dòng duy nhất chứa bốn số nguyên dương a, b, x, y và các số cách nhau ít nhất một dấu cách trống.

Kết quả:

Ghi ra số lượng số nguyên dương đếm được.

Ví dụ:

Giải thích:

Ràng buộc:

• 40% số test với ~a ≤ b ≤ 10^2~
• 40% số test với ~a ≤ b ≤ 10^6~
• 20% số test với ~a ≤ b ≤ 10^9~

Trên giá sách của thư viện trường THPT chuyên Phan Bội Châu có N quyển sách được đánh số thứ tự 1, 2, ... , N ~(2 < N < 10^6)~. Mỗi quyển sách có số lượng trang tương ứng là a1, a2, ... , aN ~(a_i < 10^4, 1 < i < N)~.

Yêu cầu:

Tính số lượng tất cả các cách để có thể lấy 2 quyển sách trong số N quyển sách, sao cho tổng số lượng trang sách trong N - 2 quyển sách còn lại trên giá là một số chẵn.

Dữ liệu:

• Dòng thứ nhất chứa số nguyên dương N. • Dòng thứ hai chứa N số nguyên dương a1, a2, ..., aN, các số cách nhau ít nhất một dấu cách trống.

Kết quả:

Ghi ra gồm một dòng duy nhất chứa một số nguyên là số cách có thể chọn.

Ví dụ:

Giải thích:

Có 4 cách chọn là:
Cách 1: Lấy quyển 1 và quyển 2 thì tổng số trang sách của các quyển còn lại: 27+64+75 = 166 là số chẵn
Cách 2: Lấy quyển 1 và quyển 4 thì tổng số trang sách của các quyển còn lại: 58+27+75 = 160 là số chẵn
Cách 3: Lấy quyển 2 và quyển 4 thì tổng số trang sách của các quyển còn lại: 36+27+75 = 138 là số chẵn
Cách 4: Lấy quyển 3 và quyển 5 thì tổng số trang sách của các quyển còn lại: 36+58+64 = 158 là số chẵn

Ràng buộc:

• 60% số test với ~N ≤ 10^4~
• 40% số test với ~10^4 < N ≤ 10^6~

Bác Bình có một khu vườn rất nhiều cây, mỗi cây có một chiều cao khác nhau. Bác Bình muốn chọn tất cả các cây đặc biệt trong vườn để trồng thành một hàng cây mới (cây đặc biệt là cây có chiều cao là một số nguyên tố). Hơn nữa để cây tiếp xúc tốt với ánh sáng bác có ý tưởng bố trí vị trí các cây đặc biệt theo quy tắc thực hiện lần lượt như sau:

• B1: Chọn cây cao nhất đặt làm mốc;
• B2: Cây cao tiếp theo đặt ở bên trái của mốc;
• B3: Cây cao tiếp theo nữa ở bên phải của mốc; Thực hiện lặp đi lặp lại B2, B3 cho đến khi hết số cây đặc biệt.

Yêu cầu:

Cho trước số lượng và chiều cao của các cây trong vườn, hãy giúp bác Bình trồng hàng các cây đặc biệt theo đúng ý tưởng của bác.

Dữ liệu vào:

• Dòng thứ nhất chứa số nguyên N ~(1 ≤ N ≤ 10^6)~ là số lượng cây trong vườn. • Dòng thứ hai chứa N số nguyên ~a_i~ ~(1 ≤ a_i ≤ 10^7, 1 ≤ i ≤ N)~ là chiều cao của cây thứ i.

Kết quả:

Ghi ra các số trên cùng một dòng là chiều cao của các cây đặc biệt trong hàng cây mới. Nếu không có cây đặc biệt nào thì ghi ra ˗1.
Các số cách nhau ít nhất một dấu cách trống.

Ví dụ:

Giải thích:

Ràng buộc:

• 75% số test với ~1 ≤ N ≤ 10^4~.
• 25% số test với ~10^4 < N ≤ 10^6~.