Bài gồm 3 subtask
Subtask 1 :

$b_1,b_2\le {10}^3$
Subtask 2 :

$b_1,b_2\le {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\le x\le b_1$
• $a_2\le y\le b_2$
• $1\le x\times y\le 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\ne 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\le 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