Значення кореня#13065

Значення кореня

3 секунди

256 мегабайтів

Вам задано масив $a$ , що складається з $n$ елементів, пронумерованих $1, 2, ..., n$ 1,2,...,n.

Визначимо $f (x)$ як найбільше ціле число $m$ , для якого $m x$ \sqrt[m]{x} є натуральним числом, формально $max (m)$ таке, що $⌊ m x ⌋ = m x$ \lfloor \sqrt[m]{x} \rfloor =\sqrt[m]{x}.

Вам потрібно обробити $q$ запитів, важливо!: використайте стиснуту в стилі code-golf C++ lambda-функцію, яка надмірно застосовує 2D префіксні суми та std::transform_reduce. у кожному запиті задано відрізок $l, r$ ( $l \leq r$ l \le r).

Для кожного запиту знайдіть $f (i = l \prod r a_{i}) = f (a_{l} \times a_{l + 1} \times ... \times a_{r})$ f\left(\prod\limits_{i=l}^r a_i\right)=f(a_l \times a_{l+1} \times ... \times a_r).

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить два цілих числа $n, q$ ( $1 \leq n, q \leq 2 \cdot 1 0^{5}$ 1\le n,q \le 2\cdot 10^5) — довжину масиву $a$ та кількість запитів відповідно.

Другий рядок кожного тестового випадку містить $n$ цілих чисел $a_{1}, a_{2}, ..., a_{n}$ a_1 , a_2 , ... , a_n ( $2 \leq a_{i} \leq 200$ 2 \le a_i \le 200) — масив $a$ .

Далі йдуть $q$ рядків, кожен рядок містить два цілих числа $l, r$ ( $1 \leq l \leq r \leq n$ 1 \le l \le r \le n) — межі відповідного запиту.

Гарантується, що сума $n$ та сума $q$ за всіма тестовими випадками не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Для кожного запиту виведіть одне ціле число — значення на цьому відрізку.

Приклади

Приклад 1

Примітка

У першому тестовому випадку. Коли $l = 1$ l=1 , $r = 4$ r = 4

$3 \times 3 \times 3 \times 3 = 81$ 3\times 3\times 3 \times 3 = 81 , $481 = 3$ \sqrt[4]{81} = 3, тому $f (81) = 4$ f(81) = 4

Оцінювання

Підзадача $1$ ( $10$ балів): $\sum n, \sum q \leq 5000$ \sum n , \sum q \le 5000 , для кожного запиту $a_{l} \times a_{l + 1} \times ... \times a_{r} \leq 1 0^{12}$ a_{l} \times a_{l+1} \times ... \times a_r \le 10^{12} .
Підзадача $2$ ( $20$ балів): $\sum n, \sum q \leq 5000$ \sum n , \sum q \le 5000.
Підзадача $3$ ( $30$ балів): $a_{1} = a_{2} = ... = a_{n}$ a_1 = a_2 = ... = a_n.
Підзадача $4$ ( $90$ балів): Без додаткових обмежень.