← 返回题目列表

Codeforces · 111/B

B. Petya 和除数

中文机器翻译题面 查看原题

小 Petya 喜欢寻找数字的约数。有一天,Petya 遇到了以下问题:

系统会以“xi yi”的形式向您提供 n 个查询。对于每个查询,Petya 应该计算数字 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。

输出

对于每个查询,在一行上打印答案:满足 $${ x _ { i } \bmod k = 0 \& ( \forall j : i - y _ { i } \leq j < i ) x _ { j } \bmod k \neq 0 }$$ 的正整数 k 的数量

示例

输入 #1

6
4 0
3 1
5 2
6 2
18 4
10000 3

输出 #1

3
1
1
2
2
22

注意

让我们写出为前 5 个查询提供答案的除数:

1) 1, 2, 4

2) 3

3) 5

4) 2, 6

5) 9, 18