ABC-019-C 高橋くんと魔法の箱

■■■問題■■■

高橋くんは魔法の箱を持っています。
この箱に整数を入れるとそれに対応した整数が出てきます。
出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。

高橋くんは任意の整数xについて、
xを入れた時と2xを入れた時に出てくる整数が同じであることに気づきました。

高橋くんが入れた整数がN個与えられるので、最大で何種類の整数が出てくるか答えてください。

■■■入力■■■

N
a1 a2 ・・・ aN

●1行目には、高橋くんが箱に入れる整数の個数 N(1 <= N <= 10万) が与えられる。
●2行目には、高橋くんが箱に入れるN個の整数が空白を区切りとして与えられる。
●1 <= ai <= 10億(1 <= i <= N) であることが保証される。
●i≠j のとき、ai≠aj であることが保証される。

■■■出力■■■

最大で何種類の整数が出てくるかを標準出力に出力せよ。末尾の改行を忘れないこと。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("1 2 3");
            //2
            //2を入れた時に出てくる整数は、
            //1を入れた時に出てくる整数と等しいので、
            //最大で2種類の整数が出てきます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("2 4 8 16");
            //1
            //すべて同じ整数が出てきます
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4");
            WillReturn.Add("2 3 5 7");
            //4
            //出てくる整数が全て違う可能性があります
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(X => int.Parse(X)).ToArray();

        var BaseSet = new HashSet<int>();
        foreach (int EachInt in AArr) {
            int BaseVal = EachInt;
            while (BaseVal % 2 == 0) {
                BaseVal /= 2;
            }
            BaseSet.Add(BaseVal);
        }
        Console.WriteLine(BaseSet.Count);
    }
}

解説

2で割れるだけ割った結果の数が、何通りあるかを調べてます。