[AtCoder] ABC 193 C – Unexpressed

2021年2月28日

問題

方針

愚直に \( a^b \) で表される数字を数え上げます。\( b \geq 2 \) より、\( 2 \leq a \leq \sqrt{N} \) の範囲で計算すれば良いです。\( a \) を固定したとき、\( a^b \leq N \) より、\( b \leq \log_a{N} \) なので全探索を行えます。

コード

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

int main() {
    ll N;
    cin >> N;
    set<ll> s;
    for (ll a = 2; a * a <= N; a++) {
        ll x = a;
        while (x * a <= N) {
            s.insert(x * a);
            x *= a;
        }
    }
    cout << N - s.size() << "\n";
    return 0;
}