Hướng dẫn cho TLEOJ Cup 2024 - Ngày 2 - Chia kẹo

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: Sunlight

Lời giải

Subtask 1:

$V \le 10^6, H = 0$

Chỉ cần tính giá trị $(V \mod 1) + (V \mod 2) + ... + (V \mod V)$ như đề bài bằng một vòng lặp.

Subtask 2:

$H = 0$

Nhận thấy $P \mod i = P - i \times \lfloor \frac{P}{i} \rfloor$ và bài toán tính tổng $1 \times \lfloor \frac{P}{1} \rfloor + 2 \times \lfloor \frac{P}{2} \rfloor + ... + P \times \lfloor \frac{P}{P} \rfloor$ là biến thể của bài toán floor sum nên có thể áp dụng ý tưởng của bài toán floor sum để giải quyết subtask này.
Lưu ý, để tránh tràn số cần phải sử dụng phương pháp nhân nhị phân (nhân Ấn Độ).

Subtask 3:

$V + H \le 10^6$

Ta có công thức: $D(P) = D(P - 1) + (P - 1) - s(P) - P$ với $s(P)$ là tổng các ước của $P$ . Chứng minh của công thức này xin nhường cho bạn đọc.
Từ công thức trên ta có thể tạo sàng ước để tính lần lượt từng giá trị $s(P)$ từ đó tính $D(P)$

Subtask 4 + 5: Không có giới hạn gì thêm

Áp dụng subtask 2 để tính $D(V)$ và sử dụng sàng ước trên đoạn để tính tiếp các giá trị còn lại.

Bình luận

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