AtCoder Beginner Contest 186 C – Unlucky 7 を解いた記録

問題の概要

\(N\)以下の正の整数のうち,10進法で表記しても8進法で表記しても数字「7」を含まないものがいくつあるか求めよ.

問題へのリンク

制約

  • \(1 \leq N \leq 10^{5}\)
  • 入力はすべて整数

解法

ある正の整数\(A\)が10進法表記で数字「7」を含むかどうかは,以下の手順で判定できます.(10進法で表記したときの)各位の数字が何であるかを判定しています.

  • \(A\)を\(10\)で割ったあまりが\(7\)であれば,\(A\)が10進法表記で数字「7」を含むことがわかる.(判定完了)
  • \(A\)を\(10\)で割ったあまりが\(7\)でないときは,\(A\)を\(10\)で割ったもの(小数点以下切り捨て)を新しい\(A\)として1.に戻る.
    ただし新しい\(A\)が0の場合は,元々の\(A\)が10進法表記で数字「7」を含まないことがわかる.(判定完了)

また,ある正の整数\(A\)が8進法表記で数字「7」を含むかどうかは,上記の手順中の\(10\)を\(8\)に置き換えて上記の手順を実行すれば判定できます.

\(1\)から\(N\)までのすべての整数について,上記の手順により10進法表記で数字「7」を含むかどうか及び8進法表記で数字「7」を含むかどうかを判定すれば,答えにたどり着けます.

実装例