[yukicoder] No. 638 Sum of “not power of 2”

2019年6月5日

問題

方針

\( 2^{k} \leq 10^{18}\) を満たす正の整数 \( k \) は \( 60 \) 個程度なので、この組み合わせを全探索します。あらかじめ \( 2^k \) の配列を作成し、二重ループで探索すれば十分です。

この探索で条件を満たす \( a, b\) が存在するとき、\( a = 3 \) から順番に値を増やしていき、\(  a \) と \( b = N – a \) が \( 2^k \) とならない \( a \) が答えになります。

コード

提出したコード

全探索

  set<ll> s;
  s.insert(1);
  ll t = 2;

  while (t <= N) {
    s.insert(t);
    t *= 2;
  }
  for (int i = 3; i < N; i++) {
    if (s.count(i) == 0) {
      if (s.count(N - i) == 0) {
        cout << i << " " << N - i << "\n";
        return 0;
      }
    }
  }
  cout << "-1" << "\n";