Sad powers [Codeforces Round #471 (Div. 2) C]

http://codeforces.com/contest/955/problem/C

Q個のクエリに答えよ。
「x=[L,R]の範囲で整数a,pでx=a^pかつa＞0,p＞1と表現できる数の個数を答えよ」

解法

http://codeforces.com/contest/955/submission/36558558

まず、[L,R]の区間のクエリであるためf(R)-f(L-1)で答えることにしよう。
f(x) := [0,x]の範囲で条件を満たす数の個数は？
関数fを作っていくが、方針としては「平方数とそれ以外に分けて数える」ことにする。
　
まずは平方数であるが、これは二分探索で何個あるか数えよう。
オーバーフローに注意。
　
では、それ以外を数えよう。
重要な事実がある「最大が10^18であれば、立方数は10^6個以下になる」
そのため、3乗の数,5乗の数,7乗の数,...を全列挙できる。
aが平方数であれば、3乗の数なども平方数となってしまうので、aが平方数でなく、pが3以上の奇数で全列挙する。
あとは、ソートしてダブっている部分を消しておくと、関数fではupper_boundで境界を探すだけで個数が得られる。

int Q;
//---------------------------------------------------------------------------------------------------
vector<ll> v;
void pre() {
    rep(a, 2, 1010101) if (!isSquare(a)) {
        ll x = 1LL * a * a * a;
        ll y = 1LL * a * a;
        v.push_back(x);
        while (1.0 * x * y < 2e18) {
            x *= y;
            v.push_back(x);
        }
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
}
ll f(ll x) {
    if (x == 0) return 0;
    ll res = upper_bound(all(v), x) - v.begin();

    ll ok = 1, ng = 1e9+5;
    while (ok + 1 != ng) {
        ll md = (ok + ng) / 2;
        if (md*md <= x) ok = md;
        else ng = md;
    }
    res += ok;

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    pre();

    cin >> Q;
    rep(q, 0, Q) {
        ll L, R;
        cin >> L >> R;
        ll ans = f(R) - f(L - 1);
        printf("%lld\n", ans);
    }
}