DDOSvoid's Blog

CF 955C Sad powers

发表于 更新于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

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

简要题意：现在有 $q$ 个询问，每次询问区间 $[l,r]$ 内有多少个满足条件的 $x=a^p(a>0,p>1)$

$q\le 10^5,1\le l\le r\le 10^{18}$

Solution

首先将区间询问转换成前缀差分，然后我们发现对于 $p\ge 3$ 数会很少，大概是 $O(10^6)$，这个东西可以直接预处理，而对于 $p=2$ 的数，直接就等于 $\lfloor\sqrt n\rfloor$，注意 $cmath$ 自带的 $sqrt$ 精度不太行，可以手写一个二分来开根或者使用 $sqrtl$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;

int n;

ll root(ll x) {
    ll l = 0, r = 1000000000, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (mid * mid <= x) ans = mid, l = mid + 1;
        else r = mid - 1; 
    } return ans;
}

vector<ll> A; 
void init(ll n) {
    for (ll i = 2; i * i <= n / i; ++i) {
        ll t = i * i;
        while (t <= n / i) {
            t *= i;
            ll s = root(t); 
            if (s * s != t) A.push_back(t);
        }
    } 
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end()); 
}

ll calc(ll n) {
    return root(n) + upper_bound(A.begin(), A.end(), n) - A.begin();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    
    cin >> n; init(1000000000000000000); 
    for (int i = 1; i <= n; ++i) {
        ll l, r; cin >> l >> r;
        cout << calc(r) - calc(l - 1) << "\n";
    }
    return 0; 
}

​