Ước số (uocsotht.*)

Một số nguyên dương \(n\) được phân tích thành thừa số nguyên tố như sau:

\[n = p_{1}^{k_{1}} \times p_{2}^{k_{2}} \times \ldots \times p_{m}^{k_{m}}\]

Yêu cầu: Cho hai số nguyên không âm \(a \leq b\), dếm số lượng ước số của \(n\) thuộc \(\lbrack a,b\rbrack\).

Dữ liệu vào:

+ Dòng đầu chứa số nguyên dương \(m\)

+ Tiếp theo là \(m\) dòng, dòng thứ \(i\) chứa hai số nguyên dương \(p_{i}\) và \(k_{i}\), trong đó \(p_{i},\ k_{i}\) không vượt quá \(10^{9}\) và các số \(p_{i}\) là số nguyên tố đôi một khác nhau;

+ Ba dòng cuối tương ứng với ba câu hỏi, mỗi dòng chứa hai số nguyên không âm \(a,b\) tương ứng một câu hỏi.

Kết quả:

+ Ghi trên ba dòng, mỗi dòng ghi ước số tìm được trả lời cho câu hỏi tương ứng ở dữ liệu vào.

Ví dụ:

Ràng buộc:

+ Có 40% số test ứng với \(m \leq 5;0 \leq a \leq b \leq 10^{6}\)

+ Có 40% số test ứng với \(m \leq 10;0 \leq a \leq b \leq 10^{9}\)

+ Có 20% số test ứng với \(m \leq 25;0 \leq a \leq b \leq 10^{9}\)