Bedao Regular Contest 04 - LOG LCM

View as PDF

Submit solution


Points: 0.60 (partial)
Time limit: 1.5s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

~iostream~ giao cho ~tahp~ viết content cho ~Bedao \ Regular \ 04~. Thế nhưng vốn từ quá ít ỏi cộng thêm tâm hồn khô khan khiến cho ~tahp~ không thể nào viết được một câu chuyện hay để hấp dẫn mọi người. Vì thế ~tahp~ quyết định viết đề bài một cách đơn giản như cách làm của bài này vậy. Đề bài như sau:

Cho mảng ~a~ gồm ~n~ số nguyên dương đánh số từ ~1~ đến ~n~, bạn phải trả lời các truy vấn sau :

Với mỗi truy vấn cho ~1~ cặp số ~L~, ~R~, hãy đếm số lượng giá trị nguyên ~x~ sao cho ~log_x(LCM(a[L..R]))~ là một số nguyên dương.

Chú ý : ~LCM(a[L..R])~ là bội chung nhỏ nhất của tất cả các phần tử trong mảng ~a[1..n]~ có chỉ số thuộc đoạn ~[L, R]~.

Tất nhiên vì bài trên quá đơn giản để làm E của regular 4 nên bạn cần trả lời truy vấn theo 1 cách khác:

  • cho ~q~ nhóm truy vấn, mỗi nhóm được biểu thị bởi ~1~ cặp số ~k~, ~R~. Kết quả của một nhóm truy vấn là tổng kết quả của mọi truy vấn ~L~, ~R~ sao cho ~k \le L \le R~.

Ví dụ : kết quả của nhóm truy vấn ~[3, 5]~ ~(k = 3, R = 5)~ là tổng kết quả các truy vấn ~[3, 5]~, ~[4, 5]~ và ~[5, 5]~.

Input

  • Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 5 \times 10^5, q \le 10^5)~.

  • Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ ~(a_i \le 4 \times 10^6)~.

  • ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~k~, ~R~ thể hiện một nhóm truy vấn ~(1 \le k \le R \le n)~.

Output

  • In ra ~q~ dòng, mỗi dòng là kết quả tương ứng của một nhóm truy vấn.

Sample Input

5 3
1 2 9 12 16
1 2
2 4
5 5

Sample Output

2
5
3

Subtask

  • ~10\%~ số test có ~q = 1~, có duy nhất 1 nhóm truy vấn là ~[1, n]~
  • ~30\%~ số test khác có ~a_i~ là một lũy thừa của ~2~ và mọi nhóm truy vấn đều có ~k~ = 1.
  • ~60\%~ số test còn lại không có điều kiện gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.