Biểu ngữ lớn

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(|dx|,|dy|)=1$ với $(dx,dy)$ là vector hướng. Với mỗi vector $(a,b)$ thỏa $gcd(a,b)=1$ và $L\le \sqrt{a^2+b^2}\le 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

1. 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.
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$.
3. Mỗi số $a\le {10}^5$ có ít nhất $7$ ước nguyên tố phân biệt, nên số subset của primes $\le 2^7=128$.

Thuật toán

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

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

Độ phức tạp

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