Ước số (THTB Vòng Sơ loại)

Xem PDF

Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

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} × p_2^{k_2} × ... × p_m^{k_m}\)

Yêu cầu: Cho hai số nguyên không âm \(A \le B\), đếm số lượng ước của \(n\) trong đoạn \([A, B]\).

Input

Vào từ thiết bị vào chuẩn có khuôn dạng:

  • 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\)\(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 với một câu hỏi.

Output

  • Ghi ra thiết bị ra chuẩ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.

Scoring

  • Subtask \(1\) (%40\%$ số điểm): \(m \le 5; 0 \le A \le B \le 10^6\);
  • Subtask \(2\) (%40\%$ số điểm): \(m \le 10; 0 \le A \le B \le 10^9\);
  • Subtask \(3\) (%20\%$ số điểm): \(m \le 25; 0 \le A \le B \le 10^9\)

Example

Test 1

Input
3
2 4
3 4
5 4
1 5
1 10
1 5
Output
5
9
5

Bình luận


  • 8
    1805    8:17 p.m. 8 Tháng 10, 2021

    ai có thể viết editorial được không ạ, em nghĩ mãi không ra :<