Hướng dẫn giải của Biểu ngữ lớn

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Biểu ngữ lớn

Hướng tiếp cận

Không đi qua cọc trung gian tương đương với $gcd (| d x |, | d y |) = 1$ với $(d x, d y)$ là vector hướng. Với mỗi vector $(a, b)$ thỏa $gcd (a, b) = 1$ và $L \leq \sqrt{a^{2} + b^{2}} \leq H$ , số đoạn thẳng theo hướng này là $(M - a + 1) (N - b + 1)$ .

Nhận xét quan trọng

Với hướng $(a, b)$ và $(a, - b)$ (cả hai đều hợp lệ khi $b > 0$ ), số đoạn thẳng nhân 2.
Để đếm số $b$ trong $[b_{min}, b_{max}]$ thỏa $gcd (a, b) = 1$ : dùng bao hàm-loại trừ trên các ước nguyên tố của $a$ .
Mỗi số $a \leq 10^{5}$ có ít nhất $7$ ước nguyên tố phân biệt, nên số subset của primes $\leq 2^{7} = 128$ .

Thuật toán

Với mỗi $a$ từ $0$ đến $min (M, H)$ :

Tính khoảng $b$ hợp lệ: $b_{min} = ⌈ \sqrt{L^{2} - a^{2}} ⌉$ , $b_{max} = ⌊ \sqrt{H^{2} - a^{2}} ⌋$ .
Phân tích thừa số nguyên tố của $a$ .
Dùng bao hàm-loại trừ để tính $\sum_{b \in [b_{min}, b_{max}], gcd (a, b) = 1} (N - b + 1)$ .
Nhân với $(M - a + 1) \times 2$ (hai chiều).

Độ phức tạp

Thời gian: $O (M \cdot 2^{ω (a)})$ trong đó $ω (a) \leq 7$ — thực tế rất nhanh.
Bộ nhớ: $O (1)$

Bình luận

Không có bình luận tại thời điểm này.