105 [AtCoder Beginner Contest 106 B]

https://beta.atcoder.jp/contests/abc106/tasks/abc106_b

解法

https://beta.atcoder.jp/contests/abc106/submissions/3039853

約数列挙をする。
enumdiv(n) := nの約数の配列を返す
これはi≦nを満たすiで全探索すればO(n)で実装できる。
しかし、後々のことを考えるとO(sqrt(n))のenumdivを用意しよう。

vector<int> enumdiv(int n) { 
    vector<int> S;
    for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
    sort(S.begin(), S.end());
    return S;
}

iが約数であれば、n/iも約数になることを利用すると、iをnまでではなく、sqrt(n)まで見れば十分になる。
これで計算量がO(sqrt(n))で抑えられる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
 
    int ans = 0;
    rep(i, 1, N + 1) if (i % 2 == 1) {
        auto ed = enumdiv(i);
        if (ed.size() == 8) ans++;
    }
    cout << ans << endl;
}