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

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

2020-04-12

AtCoder ABC 106 B - 105 (灰色, 200 点)

AtCoder AtCoder200点 ABC-B 全探索数学(整数問題) 約数灰色diff for文多重for文【問題集】整数変数の式で表された条件を扱う探索全探索:考えられる整数値を全探索易しい全探索 for文:条件を満たす添字やその個数を求める算数と数学易しい整数問題そのまま覚えたい易しい教育的典型問題

E8君問題集の第2問

問題へのリンク

問題概要

正の整数 $N$ が与えられる。 $1$ 以上 $N$ 以下の整数のうち、約数の個数がちょうど 8 個あるものが何個あるかを求めよ。

制約

$1 \le N \le 200$

考えたこと

単純に 1 から $N$ までの整数それぞれについて、

約数をすべて求めて
それが 8 個かどうかを調べる

という風にすれば OK。整数 $n$ の約数列挙は、以下の記事に解説したような方法で $O(\sqrt{n})$ でできる。

qiita.com

しかし今回は制約が緩いため、もっと簡単な方法で $O(n)$ かけてしまってもよい。具体的には

$i = 1, 2, \dots, n$ のそれぞれについて、
$n$ が $i$ で割り切れるかどうかを調べる

という風にすれば OK。全体の計算量は $O(N^{2})$ 。

c++

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

int main() {
    int N;
    cin >> N;
    int res = 0;
    for (int n = 1; n <= N; n += 2) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) if (n % i == 0) ++cnt;
        if (cnt == 8) ++res;
    }
    cout << res << endl;
}

python

N = int(input())
res = 0
for n in range(1, N+1, 2):
    cnt = 0
    for i in range(1, n+1):
        if n % i == 0:
            cnt += 1
    if cnt == 8:
        res += 1
print(res)