309767: CF1732D1. Balance (Easy version)
Memory Limit：256 MB
Time Limit：3 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Balance (Easy version)
题意翻译
有一个整数集合，初始只有一个元素 $0$，有两种操作，分别形如 `+ x` 和 `? k`。第一种操作的含义是在集合中加入一个元素 $x$，第二种是希望找出最小的整数 $t$，使得 $t\times k$ 不在集合内。题目描述
This is the easy version of the problem. The only difference is that in this version there are no "remove" queries. Initially you have a set containing one element — $ 0 $ . You need to handle $ q $ queries of the following types: - + $ x $ — add the integer $ x $ to the set. It is guaranteed that this integer is not contained in the set; - ? $ k $ — find the $ k\text{-mex} $ of the set. In our problem, we define the $ k\text{-mex} $ of a set of integers as the smallest non-negative integer $ x $ that is divisible by $ k $ and which is not contained in the set.输入输出格式
输入格式
The first line contains an integer $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of queries. The following $ q $ lines describe the queries. An addition query of integer $ x $ is given in the format + $ x $ ( $ 1 \leq x \leq 10^{18} $ ). It is guaranteed that $ x $ was not contained in the set. A search query of $ k\text{-mex} $ is given in the format ? $ k $ ( $ 1 \leq k \leq 10^{18} $ ). It is guaranteed that there will be at least one query of type ?.
输出格式
For each query of type ? output a single integer — the $ k\text{-mex} $ of the set.
输入输出样例
输入样例 #1
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000输出样例 #1
3
6
3
3
10
3
2000000000000000000输入样例 #2
6
+ 100
? 100
+ 200
? 100
+ 50
? 50输出样例 #2
200
300
150说明
In the first example: After the first and second queries, the set will contain elements $ \{0, 1, 2\} $ . The smallest non-negative number that is divisible by $ 1 $ and is not contained in the set is $ 3 $ . After the fourth query, the set will contain the elements $ \{0, 1, 2, 4\} $ . The smallest non-negative number that is divisible by $ 2 $ and is not contained in the set is $ 6 $ . In the second example: - Initially, the set contains only the element $ \{0\} $ . - After adding an integer $ 100 $ the set contains elements $ \{0, 100\} $ . - $ 100\text{-mex} $ of the set is $ 200 $ . - After adding an integer $ 200 $ the set contains elements $ \{0, 100, 200\} $ . - $ 100\text{-mex} $ of the set is $ 300 $ . - After adding an integer $ 50 $ the set contains elements $ \{0, 50, 100, 200\} $ . - $ 50\text{-mex} $ of the set is $ 150 $ .Input
题意翻译
有一个整数集合，初始只有一个元素 $0$，有两种操作，分别形如 `+ x` 和 `? k`。第一种操作的含义是在集合中加入一个元素 $x$，第二种是希望找出最小的整数 $t$，使得 $t\times k$ 不在集合内。Output
题目大意：
这是一个简单的平衡问题版本。初始时，你有一个只包含一个元素——0的集合。需要处理q个查询，查询类型如下：
- + x —— 向集合中添加整数x。保证这个整数不在集合中；
- ? k —— 找出集合的k-mex。
在这个问题中，我们将一个整数集合的k-mex定义为最小的非负整数x，它能够被k整除且不在集合中。
输入输出数据格式：
输入格式：
第一行包含一个整数q（1≤q≤2×10^5）——查询的数量。
接下来的q行描述了查询。
添加整数x的查询格式为+x（1≤x≤10^18）。保证x不在集合中。
k-mex的搜索查询格式为?k（1≤k≤10^18）。
保证至少有一个类型为?的查询。
输出格式：
对于每个类型为?的查询，输出一个整数——集合的k-mex。
输入输出样例：
输入样例 #1：
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
输出样例 #1：
3
6
3
3
10
3
2000000000000000000
输入样例 #2：
6
+ 100
? 100
+ 200
? 100
+ 50
? 50
输出样例 #2：
200
300
150
说明：
在第一个例子中：
- 在前两个查询之后，集合将包含元素{0, 1, 2}。最小的非负数，它能够被1整除且不在集合中是3。
- 在第四个查询之后，集合将包含元素{0, 1, 2, 4}。最小的非负数，它能够被2整除且不在集合中是6。
在第二个例子中：
- 初始时，集合只包含元素{0}。
- 添加整数100后，集合包含元素{0, 100}。
- 集合的100-mex是200。
- 添加整数200后，集合包含元素{0, 100, 200}。
- 集合的100-mex是300。
- 添加整数50后，集合包含元素{0, 50, 100, 200}。
- 集合的50-mex是150。题目大意： 这是一个简单的平衡问题版本。初始时，你有一个只包含一个元素——0的集合。需要处理q个查询，查询类型如下： - + x —— 向集合中添加整数x。保证这个整数不在集合中； - ? k —— 找出集合的k-mex。 在这个问题中，我们将一个整数集合的k-mex定义为最小的非负整数x，它能够被k整除且不在集合中。 输入输出数据格式： 输入格式： 第一行包含一个整数q（1≤q≤2×10^5）——查询的数量。 接下来的q行描述了查询。 添加整数x的查询格式为+x（1≤x≤10^18）。保证x不在集合中。 k-mex的搜索查询格式为?k（1≤k≤10^18）。 保证至少有一个类型为?的查询。 输出格式： 对于每个类型为?的查询，输出一个整数——集合的k-mex。 输入输出样例： 输入样例 #1： 15 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 1000000000000000000 ? 1000000000000000000 输出样例 #1： 3 6 3 3 10 3 2000000000000000000 输入样例 #2： 6 + 100 ? 100 + 200 ? 100 + 50 ? 50 输出样例 #2： 200 300 150 说明： 在第一个例子中： - 在前两个查询之后，集合将包含元素{0, 1, 2}。最小的非负数，它能够被1整除且不在集合中是3。 - 在第四个查询之后，集合将包含元素{0, 1, 2, 4}。最小的非负数，它能够被2整除且不在集合中是6。 在第二个例子中： - 初始时，集合只包含元素{0}。 - 添加整数100后，集合包含元素{0, 100}。 - 集合的100-mex是200。 - 添加整数200后，集合包含元素{0, 100, 200}。 - 集合的100-mex是300。 - 添加整数50后，集合包含元素{0, 50, 100, 200}。 - 集合的50-mex是150。
这是一个简单的平衡问题版本。初始时，你有一个只包含一个元素——0的集合。需要处理q个查询，查询类型如下：
- + x —— 向集合中添加整数x。保证这个整数不在集合中；
- ? k —— 找出集合的k-mex。
在这个问题中，我们将一个整数集合的k-mex定义为最小的非负整数x，它能够被k整除且不在集合中。
输入输出数据格式：
输入格式：
第一行包含一个整数q（1≤q≤2×10^5）——查询的数量。
接下来的q行描述了查询。
添加整数x的查询格式为+x（1≤x≤10^18）。保证x不在集合中。
k-mex的搜索查询格式为?k（1≤k≤10^18）。
保证至少有一个类型为?的查询。
输出格式：
对于每个类型为?的查询，输出一个整数——集合的k-mex。
输入输出样例：
输入样例 #1：
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
输出样例 #1：
3
6
3
3
10
3
2000000000000000000
输入样例 #2：
6
+ 100
? 100
+ 200
? 100
+ 50
? 50
输出样例 #2：
200
300
150
说明：
在第一个例子中：
- 在前两个查询之后，集合将包含元素{0, 1, 2}。最小的非负数，它能够被1整除且不在集合中是3。
- 在第四个查询之后，集合将包含元素{0, 1, 2, 4}。最小的非负数，它能够被2整除且不在集合中是6。
在第二个例子中：
- 初始时，集合只包含元素{0}。
- 添加整数100后，集合包含元素{0, 100}。
- 集合的100-mex是200。
- 添加整数200后，集合包含元素{0, 100, 200}。
- 集合的100-mex是300。
- 添加整数50后，集合包含元素{0, 50, 100, 200}。
- 集合的50-mex是150。题目大意： 这是一个简单的平衡问题版本。初始时，你有一个只包含一个元素——0的集合。需要处理q个查询，查询类型如下： - + x —— 向集合中添加整数x。保证这个整数不在集合中； - ? k —— 找出集合的k-mex。 在这个问题中，我们将一个整数集合的k-mex定义为最小的非负整数x，它能够被k整除且不在集合中。 输入输出数据格式： 输入格式： 第一行包含一个整数q（1≤q≤2×10^5）——查询的数量。 接下来的q行描述了查询。 添加整数x的查询格式为+x（1≤x≤10^18）。保证x不在集合中。 k-mex的搜索查询格式为?k（1≤k≤10^18）。 保证至少有一个类型为?的查询。 输出格式： 对于每个类型为?的查询，输出一个整数——集合的k-mex。 输入输出样例： 输入样例 #1： 15 + 1 + 2 ? 1 + 4 ? 2 + 6 ? 3 + 7 + 8 ? 1 ? 2 + 5 ? 1 + 1000000000000000000 ? 1000000000000000000 输出样例 #1： 3 6 3 3 10 3 2000000000000000000 输入样例 #2： 6 + 100 ? 100 + 200 ? 100 + 50 ? 50 输出样例 #2： 200 300 150 说明： 在第一个例子中： - 在前两个查询之后，集合将包含元素{0, 1, 2}。最小的非负数，它能够被1整除且不在集合中是3。 - 在第四个查询之后，集合将包含元素{0, 1, 2, 4}。最小的非负数，它能够被2整除且不在集合中是6。 在第二个例子中： - 初始时，集合只包含元素{0}。 - 添加整数100后，集合包含元素{0, 100}。 - 集合的100-mex是200。 - 添加整数200后，集合包含元素{0, 100, 200}。 - 集合的100-mex是300。 - 添加整数50后，集合包含元素{0, 50, 100, 200}。 - 集合的50-mex是150。