分数: 300 点
问题陈述
给你一个序列 A = (A_1, A_2, ..., A_N).
您只能执行一次以下操作。
- 选择一个整数 M 至少 2。然后,对于每个整数 i (1 \leq i \leq N),替换 A_i 与余数当 A_i 除以 M.
例如,如果 当以下情况时选择 M = 4 被选择时 A = (2, 7, 4), A 变为 (2 \bmod 4, 7 \bmod 4, 4 \bmod 4) = (2, 3, 0).
找出不同元素的最小可能数量 A 操作后。
约束
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
3 1 4 8
示例输出 1
2
如果您选择 M = 3,你将有 A = (1 \bmod 3, 4 \bmod 3, 8 \bmod 3) = (1, 1, 2),其中 A 包含两个不同的元素。
中不同元素的数量 A 不能成为 1,所以答案是 2.
示例输入 2
4 5 10 15 20
示例输出 2
1
如果您选择 M = 5,你将有 A = (0, 0, 0, 0),这是最佳的。
示例输入 3
10 3785 5176 10740 7744 3999 3143 9028 2822 4748 6888
示例输出 3
1