問題概要

$1$ 以上 $N$ 以下の整数のうち、10 進法で表しても 8 進法で表しても 7 を含まないようなものの個数を求めよ。

制約

$1 \le N \le 10^{5}$

考えたこと

まず、整数 $n$ が与えられたときに、それを 10 進法で表したときの各桁の値を知る方法は次のようにしてできる。

int func(int n) {
    while (n) {
        int val = n % 10; // 桁の値
        n /= 10;
    }
}

たとえば $n = 4649$ のとき、

4649 を 10 で割ったあまり → 9 が取り出される
4649 を 10 で割って 464 とする
464 を 10 で割ったあまり → 4 が取り出される
464 を 10 で割って 46 とする
46 を 10 で割ったあまり → 6 が取り出される
46 を 10 で割って 4 とする
4 を 10 で割ったあまり → 4 が取り出される
4 を 10 で割って 0 とする
終了

という感じになる。こうして、9, 4, 6, 4 が順に取り出されることになる。この中に 7 が含まれたらダメ。

8 進法でもまったく同様にできる。具体的には、上のコードにおいて、「10」のところを「8」に書き換えれば OK。

なお、10 進法や 8 進法の表現を得るのに要する計算量は $O(\log n)$ となる。この計算量であれば $1$ 以上 $N$ 以下の整数 $n$ をすべて愚直に調べても間に合う。

コード

計算量は $O(N \log N)$ 。

#include <bits/stdc++.h>
using namespace std;

bool ok(int v, int b) {
    while (v) {
        if (v % b == 7) return false;
        v /= b;
    }
    return true;
}

int main() {
    int N; cin >> N;
    int res = 0;
    for (int n = 1; n <= N; ++n) {
        if (ok(n, 10) && ok(n, 8)) ++res;
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 186 C - Unlucky 7 (灰色, 300 点)

問題概要

制約

考えたこと

コード