[AtCoder] ABC 186 C – Unlucky 7

問題

方針

\( n \) 進数に変換したときに \( 7 \) が現れるかを見たいので、繰り返して剰余を計算すれば良いです。自然数 \(x \) を \( n \) 進数で表した時、各位の数字を \( a_i \) とすると、

\[ x = a_1 + a_2n + a_3n^2 + a_4n^3 + \cdots \]

と表現されるので、

\[ a_i = \left \lfloor \dfrac{x}{n^{i -1}} \right \rfloor \bmod n \]

と計算できます。

コード

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

bool contain(int n, int m) {
    while (n > 0) {
        if (n % m == 7) return true;
        n /= m;
    }
    return false;
}

int main() {
    int N;
    cin >> N;
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (!contain(i, 10) && !contain(i, 8)) cnt++;
    }
    cout << cnt << "\n";
    return 0;
}