[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; }
ディスカッション
ピンバック & トラックバック一覧
[…] [AtCoder] ABC 186 C – Unlucky 7 | ヤマカサの競技プログラミング (yamakasa.net) […]