[CF955C] Sad powers

[CF955C] Sad powers - 二分

Description

给你q个询问(1 <= q <=1e5),每次询问l到r这个区间内(1 <= l <= r <= 1e18),满足x=a^p的x的数量

Solution

首先差分转化为前缀询问，平方数个数就是开根号，高次而非平方者预处理出来，询问时二分

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

#define int long long

vector<int> vec;

bool is_square(int x)
{
    int r = sqrt(x) + 1e-9;
    if (r * r == x)
        return true;
    return false;
}

int f(int n)
{
    int ans = upper_bound(vec.begin(), vec.end(), n) - vec.begin();
    ans += sqrt(n);
    return ans;
}

void solve()
{
    int l, r;
    cin >> l >> r;
    cout << f(r) - f(l - 1) << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    for (int i = 2; i <= 1e6; i++)
    {
        for (int j = i * i * i; j <= 1e18; j *= i)
        {
            if (!is_square(j))
                vec.push_back(j);
            if (1.0 * j * i > 1.1e18)
                break;
        }
    }
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}