AtCoder Beginner Contest 19 C 高橋くんと魔法の箱

問題

atcoder.jp

問題概要

となる関数 がある。
の全ての整数をこの関数に入力した結果、何種類の整数が出力されるか答えよ。

考察

と から 。

一般化すると は任意の整数 となる。

すなわち、 となるのは を奇数になるまで2で割り続けた結果、等しくなったとき。

よって、 を奇数になるまで割り続けた結果をHashMapなどに入れておき、何種類の整数が存在するかを数えればよい。

に気づけなかったのが痛かった。

コード

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<long long> a(n);
  map<long long,int> check;
  for (int i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
  }

  for (auto& itr : a) {
    while (itr % 2 == 0) {
      itr /= 2;
    }
  }

  ll ans = 0;
  for (auto itr : a) {
    if (check[itr] == 0) {
      check[itr] = 1;
      ans += 1;
    }
  }

  cout << ans << endl;
}