Настроение Ля Вака Сатурно Сатурниты зависит от массива $$$a$$$ длины $$$n$$$, значение которого известно только ей, и функции $$$f(k, a, l, r)$$$, которую она знает, как вычислить.
Ниже представлен псевдокод функции $$$f(k, a, l, r)$$$.
function f(k, a, l, r):
ans := 0
for i from l to r (inclusive):
while k is divisible by a[i]:
k := k/a[i]
ans := ans + k
return ans
Вам даны $$$q$$$ запросов, каждый из которых содержит целые числа $$$k$$$, $$$l$$$ и $$$r$$$. Для каждого запроса выведите $$$f(k,a,l,r)$$$.
Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 10^5, 1 \leq q \leq 5\cdot 10^4$$$).
Следующая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$2 \leq a_i \leq 10^5$$$).
Следующие $$$q$$$ строк каждая содержат три целых числа $$$k$$$, $$$l$$$ и $$$r$$$ ($$$1 \leq k \leq 10^5, 1 \leq l \leq r \leq n$$$).
Гарантируется, что сумма $$$n$$$ не превышает $$$10^5$$$ по всем наборам входных данных, и сумма $$$q$$$ не превышает $$$5\cdot 10^4$$$ по всем наборам входных данных.
Для каждого запроса выведите ответ в отдельной строке.
25 32 3 5 7 112 1 52 2 42310 1 54 318 12 8 9216 1 248 2 482944 1 4
5 6 1629 13 12 520
| Codeforces Round 1017 (Div. 4) |
|---|
| Закончено |
