分数: 600 点
问题陈述
让 S 是所有正整数的集合。
流程 Q 按顺序查询。的 i-th 查询给你一个整数 A_i 不小于 2 和一个正整数 B_i,所以依次执行以下两个步骤。
- 从中删除 S 是以下倍数的所有元素 A_i.
- 打印 B_i- 第一个最小元素 S。可以证明,在给定的约束条件下, S 至少包含 此时 B_i 元素。
约束
- 1\le Q\le 10^5
- 2\le A_i\le 10^9
- 1\le B_i\le 10^5
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q A_1 B_1 \vdots A_Q B_Q
输出
打印 Q 行。的 i- 第行应包含 B_i- 第一个最小元素 S 删除所有倍数后 A_i 来自 S.
示例输入 1
5 5 10 6 1 6 10 9 10 123456789 111
示例输出 1
12 1 14 16 178
当元素 S 按升序列出,列表的开头演变如下。
- 最初, S=\lbrace 1,2,3,4,5,6,7,8,9,10,\ldots\rbrace.
- 第一个查询删除多个 5,导致 S=\lbrace1,2,3,4,6,7,8,9,11,12,\ldots\rbrace.
- 第二个查询删除多个 6,导致 S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
- 第三个查询删除多个 6,导致 S=\lbrace1,2,3,4,7,8,9,11,13,14,\ldots\rbrace.
- 第四个查询删除多个 9,导致 S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.
- 第五个查询删除多个 123456789,导致 S=\lbrace1,2,3,4,7,8,11,13,14,16,\ldots\rbrace.