← 返回题目列表

AtCoder · abc019_3

C. 高桥君和魔法盒

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

問題文

高桥君有一个魔法盒。

如果您在此框中输入一个整数,则会出现相应的整数。

出来的整数仅由您输入的整数决定,如果您输入相同的整数,则每次都会得到相同的结果。

Takahashi-kun 可以是任何整数 关于 x , 当我输入x 我注意到当我输入 2x 时,出来的整数是相同的。

高桥君输入的整数是 给出了 N ,所以请回答可以出现的最大整数个数。


入力

输入是按以下格式从标准输入给出的。

N
a_1 a_2 .. a_N
  • 1 高桥放入框中的整数个数显示在第一行。 N ( 1 ≦ N ≦ 10^5) 。 表示
  • 2 在这一排,高桥君把它放进了盒子里。 N 给出整数,用空格分隔。
  • 1 ≦ a_i ≦ 10^9 ( 1 ≦ i ≦ N) 有保证。 当
  • i ≠ j 时,a_i ≠ a_j 有保证。 当

出力

将可以出现的最大整数数输出到标准输出。

不要忘记最后的换行符。

部分点

针对此问题设置了部分分数。

  • 20 在点的测试用例中,1 ≦ N ≦ 3,000 很满意。
  • 另一个 输入 30 在点的测试用例中,1 ≦ a_i ≦ 5*10^5 ( 1 ≦ i ≦ N) 很满意。

入力例1

3
1 2 3

出力例1

2

2 时出现的整数是 它等于输入1 时得到的整数,所以最大值是 2 整数类型。


入力例2

4
2 4 8 16

出力例2

1

将出现所有相同的整数。


入力例3

4
2 3 5 7

出力例2

4

出现的整数可能都不同。