Олимпиадный тренинг

Задача . B. Петя и делители


Задача

Темы: Бинарный поиск Структуры данных теория чисел *1900

Маленький Петя любит искать делители у чисел. Однажды Петя столкнулся со следующей задачей.

Дано n запросов вида «xi yi». Для каждого запроса Пете нужно посчитать, сколько существует делителей числа xi, которые не делят ни одно из чисел xi - yi, xi - yi + 1, ..., xi - 1. Помогите ему.

Входные данные

В первой строке записано целое число n (1 ≤ n ≤ 105). В каждой из последующих n строк через пробел записано по два целых числа xi и yi (1 ≤ xi ≤ 105, 0 ≤ yi ≤ i - 1, где i — порядковый номер запроса, нумерация начинается с 1).

Ответом на запрос, для которого yi = 0, является количество делителей числа xi, при этом предыдущие числа x учитывать не следует.

Выходные данные

Для каждого запроса выведите ответ в отдельной строке: количество таких положительных целых чисел k, что

Примечание

Выпишем делители, которые дают ответ для первых 5 запросов:

1) 1, 2, 4

2) 3

3) 5

4) 2, 6

5) 9, 18


Примеры
№Входные данныеВыходные данные
1 6
4 0
3 1
5 2
6 2
18 4
10000 3 
3
1
1
2
2
22

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет