【pythonでABC186を解説】C - Unlucky 7

問題概要

問題ページ

質問用紙

高橋君は \(7\) が嫌いです。

\(1\) 以上 \(N\) 以下の整数のうち、\(10\) 進法で表しても \(8\) 進法で表しても \(7\) を含まないような数はいくつありますか？

制約

• \(1 \leq N \leq 10 ^ 5 \)
• \(N\) は整数である。

問題の考察

制約が\(1 \leq N \leq 10^5\)なので全検索することが可能。

\(n\)進数への変換divmodを使えば簡単にできる。

\(1 \leq N \leq 10^5\)なので\(8^5=32,768\)から\(8\)進数に変換した場合の最大桁数は\(5\)桁となることが分かる。

\(8^n\)は何度も使うので最初にリストを作っておくと良い。

たびすけ

\(n\)進数へ変換する場合にはdivmodを使えば簡単です。
文字列中に該当文字列があるかどうかはcountを使うとコーディングが簡単です！

ACコード

import sys

 def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    cnt = 0
    dl = [pow(8, i) for i in range(5, -1, -1)]
    for i in range(1, n + 1):
        if str(i).count("7") == 0:
            mod_v = i
            is_ok = True
            for dv in dl:
                div_v, mod_v = divmod(mod_v, dv)
                if div_v == 7:
                    is_ok = False
                    break
            if is_ok and mod_v != 7:
                cnt += 1
    print(cnt)