A16746 | Yet Another Array Problem
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
给定一个整数 $n$ 和一个长度为 $n$ 的数组 $a$。
请找出最小的整数 $x$（$2 \le x \le 10^{18}$），使得存在某个下标 $i$（$1 \le i \le n$）满足 $ \gcd^{\text{∗}}(a_i, x) = 1 $。如果在区间 $[2,10^{18}]$ 内不存在这样的 $x$，请输出 $-1$。
$^{\text{∗}}$ $ \gcd(x, y) $ 表示整数 $x$ 和 $y$ 的[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
请找出最小的整数 $x$（$2 \le x \le 10^{18}$），使得存在某个下标 $i$（$1 \le i \le n$）满足 $ \gcd^{\text{∗}}(a_i, x) = 1 $。如果在区间 $[2,10^{18}]$ 内不存在这样的 $x$，请输出 $-1$。
$^{\text{∗}}$ $ \gcd(x, y) $ 表示整数 $x$ 和 $y$ 的[最大公约数](https://en.wikipedia.org/wiki/Greatest_common_divisor)。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
接下来的 $t$ 组测试用例，每组包含两行：
第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$）。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
接下来的 $t$ 组测试用例，每组包含两行：
第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。
第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{18}$）。
保证所有测试用例中 $n$ 的总和不超过 $10^5$。
输出格式
对于每组测试用例，输出一个整数：最小的 $x$（$2 \le x \le 10^{18}$），使得存在一个下标 $i$ 满足 $ \gcd(a_i, x) = 1 $。如果区间 $[2, 10^{18}]$ 内不存在这样的 $x$，则输出 $-1$。
输入输出样例
输入 #1
4 1 1 4 6 6 12 12 3 24 120 210 4 2 4 6 10
输出 #1
2 5 5 3
在第一个测试用例中，$ \gcd(2, 1) = 1 $，这是满足条件的最小整数。
在第二个测试用例中：
- $ \gcd(2, 6) = 2 $，$ \gcd(2, 12) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 6) = 3 $，$ \gcd(3, 12) = 3 $，所以 3 不能作为答案。
- $ \gcd(4, 6) = 2 $，$ \gcd(4, 12) = 4 $，所以 4 不能作为答案。
- $ \gcd(5, 6) = 1 $，所以答案是 $5$。
在第三个测试用例中：
- $ \gcd(2, 24) = 2 $，$ \gcd(2, 120) = 2 $，$ \gcd(2, 210) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 24) = 3 $，$ \gcd(3, 120) = 3 $，$ \gcd(3, 210) = 3 $，所以 3 不能作为答案。
- $ \gcd(4, 24) = 4 $，$ \gcd(4, 120) = 4 $，$ \gcd(4, 210) = 2 $，所以 4 不能作为答案。
- $ \gcd(5, 24) = 1 $，所以答案是 $5$。
在第四个测试用例中：
- $ \gcd(2, 2) = 2 $，$ \gcd(2, 4) = 2 $，$ \gcd(2, 6) = 2 $，$ \gcd(2, 10) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 2) = 1 $，所以答案是 $3$。
在第二个测试用例中：
- $ \gcd(2, 6) = 2 $，$ \gcd(2, 12) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 6) = 3 $，$ \gcd(3, 12) = 3 $，所以 3 不能作为答案。
- $ \gcd(4, 6) = 2 $，$ \gcd(4, 12) = 4 $，所以 4 不能作为答案。
- $ \gcd(5, 6) = 1 $，所以答案是 $5$。
在第三个测试用例中：
- $ \gcd(2, 24) = 2 $，$ \gcd(2, 120) = 2 $，$ \gcd(2, 210) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 24) = 3 $，$ \gcd(3, 120) = 3 $，$ \gcd(3, 210) = 3 $，所以 3 不能作为答案。
- $ \gcd(4, 24) = 4 $，$ \gcd(4, 120) = 4 $，$ \gcd(4, 210) = 2 $，所以 4 不能作为答案。
- $ \gcd(5, 24) = 1 $，所以答案是 $5$。
在第四个测试用例中：
- $ \gcd(2, 2) = 2 $，$ \gcd(2, 4) = 2 $，$ \gcd(2, 6) = 2 $，$ \gcd(2, 10) = 2 $，所以 2 不能作为答案。
- $ \gcd(3, 2) = 1 $，所以答案是 $3$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？