← 返回题目列表

AtCoder · arc197_c

C. 删除倍数

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

分数: 600 点

问题陈述

让 S 是所有正整数的集合。

流程 Q 按顺序查询。的 i-th 查询给你一个整数 A_i 不小于 2 和一个正整数 B_i,所以依次执行以下两个步骤。

  1. 从中删除 S 是以下倍数的所有元素 A_i.
  2. 打印 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.