시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 512 MB | 0 | 0 | 0 | 0.000% |
Назовём индексом примечательности цифровой строки $S$ для заданного простого числа $P$ число различных пар позиций $i,j$ ($1 \le i \le j \le |S|$), для которых число, образованное цифрами, идущими в строке $S$ подряд c $i$-й по $j$-ю позицию включительно, делится на $P$. Число с ведущими нулями считается равным соответствующему числу без ведущих нулей.
Например, для строки 070070
и $P=13$ соответствующие пары --- $(1,1)$, $(1,5)$, $(1,6)$, $(2,5)$, $(2,6)$, $(3,3)$, $(3,4)$, $(4,4)$ и $(6,6)$. Таким образом, её индекс примечательности равен 9.
Задана цифровая строка $T$ и простое число $P$. Tребуется ответить на $q$ запросов вида <<найти индекс примечательности для подстроки $T$ с позиции $l$ по позицию $r$ включительно>>.
Первая строка содержит одно простое число $P$ ($2 \le P \le 10^9+7$). Вторая строка содержит цифровую строку $T$ ($1 \le |T| \le 10^5$). Третья строка содержит одно целое число $q$ --- число запросов ($1 \le q \le 10^5$).
Каждая из последующих $q$ строк задаёт один запрос и содержит два целых числа $l$ и $r$ --- левую и правую границу подстроки, индекс примечательности которой интересует ($1 \le l \le r \le |T|$).
Для каждого запроса выведите на отдельной строке одно целое число --- индекс примечательности соответствующей подстроки.
13 070070 3 1 6 2 5 2 2
9 4 0