Bài gồm 3 subtask
Subtask 1 : $b_1, b_2 \leq 10^3$
Subtask 2 : $b_1, b_2 \leq 10^6$
Subtask 3 : Không có giới hạn gì thêm

Lời giải bài 3 :

Subtask 1 : Trâu bò cày ruộng
Subtask 2 : Cố định miền $x$ và đếm số lượng miền $y$ thỏa mãn
Subtask 3 : Tối ưu từ Subtask 2

Gọi $f(n)$ là số lượng các cặp $(x, y)$ thỏa mãn :

- $a_1 \leq x \leq b_1$
- $a_2 \leq y \leq b_2$
- $1 \leq x \times y \leq n$

Từ đây ta tính được đáp số của bài toán là $f(b_3) - f(a_3 - 1)$.
Giờ việc của ta là tính hàm $f$ nhanh.

Cũng như Subtask 2, ta cố định miền $x$ lại, nhưng ta lại thấy rằng miền $x$ lúc này thật sự không nhỏ và việc duyệt đi nhiều lần chắc chắn sẽ dẫn tới TLE.

Đầu tiên, với một giá trị $x$, ta thấy giá trị $y_{\max}$ (bỏ qua điều kiện thỏa mãn trong đoạn $[a_2, b_2]$) sẽ là $\frac{n}{x}$ (chia làm tròn xuống)

Xét $x_1, x_2$ ($x_1 \neq x_2$), nếu $\frac{n}{x_1} = \frac{n}{x_2}$ (chia làm tròn xuống) thì số lượng miền $y$ thỏa mãn của $x_1$ và $x_2$ sẽ **bằng nhau**.

Để chứng minh thì với mỗi miền $x$, nó sẽ đóng góp vào đáp án một lượng bằng giao điểm của $[1, y_{max}]$ với $[a_2, b_2]$. Mà khi $x_1$ có cùng $y_{\max}$ với $x_2$ thì ta dễ thấy chúng có cùng **lượng đóng góp** vào đáp án. Giả sử $x_1 \leq x_2$, thì với $x \in [x_1, x_2]$ đều cũng sẽ có **cùng lượng đóng góp**.

Vậy giờ bài toán của ta với mỗi miền $x$ **thuộc cùng** $y_{\max}$, ta chỉ cần tính của một giá trị $x$ của vùng đó và nhân cho số lượng giá trị cùng vùng.

Nhưng bây giờ làm sao để ước tính số lượng vùng $y_{max}$ ?
Có một tính chất quan trọng là trong dãy số $\frac{n}{1}, \frac{n}{2}, ..., \frac{n}{n}$ (các phép chia đều làm tròn xuống) chỉ có nhiều nhất $2\sqrt{n}$ giá trị phân biệt.

Bời vì những giá trị chỉ giảm xuống khi nó gặp ước số của $n$, cùng với đó $n$ không thể nào có số ước nhiều hơn $2\sqrt{n}$ được nên ta sẽ đảm bảo được thời gian chạy.

Vậy chi phí để tính một hàm $f(n)$ lúc này là $O(2\sqrt{n} \times \log n)$
Phần $\log$ phát sinh để ta tìm những đoạn cùng $y_{\max}$

Link code : https://ideone.com/182apG