ABC293 F問題 Zero or One

atcoder.jp

b 進法での表記

N を b 進数に変換するには、それ以上割れなくなるまで繰り返し b で割り、余りを逆順に並び替えます。

この結果が、 0 , 1 のみで表される場合に条件を満たすことになります。

2進法は、必ず条件を満たします。N進法では 10, N-1進法では 11 の表記となるため条件を満たします。

制約は であり、非常に大きな値になりえるため、ひとつずつ条件を満たすか調べることはできません。

桁ごとに調べる

b が大きくなると表記は小さくなり、b が小さくなると表記は大きくなります。
そこで、 桁数k を決めて、k 桁の 100...000 以上になる b の最大値を求め、そこから b 進法の表記を調べて条件を満たすか調べながら b を 1つずつ減らしていって、表記が 111...111 を超えたら 次の桁数に変えて同じように調べることにします。
k 桁の 100...000 以上になることを式で表すと、

です。 から b を求められそうですが、N の有効桁数が 浮動小数計算の有効桁数より多くなりうるため、無視できない数値誤差が生じる可能性があります。そこで、これを満たす b の最大値を二分探索で求めます。桁あふれ(オーバーフロー)が起きないように、掛け算ではなく割り算を使う方が安全です。そして、b 進法での表記で上の桁から見ていって 0 が現れる前の 2以上の数字が表れると、111...111 を超えたとして桁数を変えます。

コード例 (Julia)

function solve_test(N)

  ans = 0

  for k = 2:100   # k = 桁数

    # b^(k-1) <= N を満たす b の上限を探す
    b_l = 1
    b_h = N+1
    while b_h - b_l > 1
      b = (b_l + b_h) ÷ 2
      M = N
      for j = 1 : k-1
        M ÷= b
      end
      if M == 0
        b_h = b
      else
        b_l = b
      end
    end

    # b を減らしながら b 進法で各桁を求めて条件を満たすか
    for b = b_l:-1:2
      M = N
      OK = true
      over = false
      for j = 1 : k-1
        R = M % b
        if R > 1
          OK = false   # 0,1 以外は条件を満たさない
          over = true
        elseif R==0
          over = false
        end
        M ÷= b
      end
      if M > 1
        OK = false
      end

      # 上の桁から見て 1 以外の最初の数字が 2 以上なら 111...111 より大きい
      # その場合ループを抜けて次の k へ
      if over
        break
      end

      if OK
        ans += 1
      end

    end

  end

  println(ans)

end  # function solve_test

function solve()

  # 入力
  readInt()  =  parse(Int,readline())

  T = readInt()

  for i = 1:T
    N = readInt()
    solve_test(N)
  end

end  # function solve


# main
solve()