C - 高橋くんと魔法の箱
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは魔法の箱を持っています。
この箱に整数を入れるとそれに対応した整数が出てきます。
出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。
高橋くんは任意の整数 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
出てくる整数が全て違う可能性があります。