← 返回题目列表

AtCoder · arc148_a

A. 模组 M

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

分数: 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