Sử dụng công thức sau: $1+2+3+...+n = \frac{n(n+1)}{2}$
Lưu ý, sử dụng kiểu dữ liệu 64-bit để lưu kết quả (long long trong C++).
Đối với subtask 1 (75%), có thể sử dụng 2 vòng lặp lồng nhau để tìm kết quả.
Đối với subtask 2: Duyệt qua tất các ký tự từ trái sáng phải. Ta sử dụng một biến “đếm” lưu lại độ dài đoạn con chỉ gồm các số 0 kết thúc tại ký tự đang đươc xét. Nếu ký tự hiện tại là 1, cập nhật biến đó về giá trị 0, ngược lại cộng thêm 1 vào biến đếm đó. Tại mỗi lần duyệt, ta lưu lại giá trị lớn nhất của biến đếm.
Một số bài tương tự: CSES - Repetitions CSES - Maximum Subarray Sum
Tham khảo trước cái bài sau: VNOI Wiki - Sàng nguyên tố LQDOJ - Tìm số nguyên tố LQDOJ - Số hồi văn
Đối với subtask 1 + 2 (70%), ta có thể làm như sau:
Duyệt qua tất cả các số từ 1 đến $10^6$. Sau đó ta cần kiểm tra số này có phải số nguyên tố đối xứng và bình phương của nó có trong đoạn $[a,b]$ hay không. Sử dụng sàng nguyên tố kiểm tra trước các số nguyên tố. Lý do chỉ duyệt đến $10^6$ vì bình phương của một số lớn hơn $10^6$ sẽ lớn hơn $10^{12}$.
Đối với subtask 3, có nhận xét như sau:
Số lượng số đối xứng có $m$ chữ số sẽ không quá $10^{\frac{m}{2}}$. Mỗi số đối xứng chỉ cần xác định bởi 1 nửa chữ số bên trái của số đó. Vì thế từ 1 đến $10^7$, số lượng số đối xứng có độ phức tạp là $O(\sqrt{10^7})$. Ta chỉ cần duyệt các số đối xứng và kiểm tra nó có phải số nguyên tố và bình phương của nó có trong đoạn hay $[a,b]$ hay không.
Kiến thức cần nắm: Quy hoạch động, Toán tổ hợp, Đồng dư.
Để xét tính trùng lặp giữa các số điện thoại, ta có thể “chuẩn hóa” lại. Với mỗi số điện thoại, ta sắp xếp lại các chữ số của nó theo thứ tự tăng dần. Những số điện thoại có tính trùng lặp, sau khi “chuẩn hóa” sẽ có giá trị giống nhau.
Đối với subtask 1 (60%), ta sẽ sử dụng đệ quy hoặc duyệt nhị phân để liệt kê ra tất cả các cách chọn nhóm. Sau đó kiểm tra số cặp tương đồng tại mỗi nhóm. Đếm số lượng nhóm có cặp tương đồng là $k$.
Đối với subtask 2, ta có hai cách làm nhưng đều sử dụng QHĐ (quy hoạch động)
$$ F[i][j] \leftarrow F[i][j-\frac{d(d+1)}{2}] \cdot \binom{w[i]}{d} $$