CF955C

· · 个人记录

题目大意：

# 解题思路： 一个经典套路是：求 $l \sim r$ 的个数=求$r$的个数-求 $l-1$ 的个数， 接下来问题转化成：如何快速查询 $1 \sim r$ 的答案？ 不难想到虽然底数很大，但是$p$不会超过$60$，所以考虑枚举$p$而算确定$p$之后底数最大多少。这样问题又来了：有可能会算重啊！比如：$64$会在幂次为$2$的时候统计一遍，在$3$的时候统计一遍，在$6$的时候又算一遍，那怎么办？ 因为会算重复，所以我们考虑容斥！而转化一下问题就变成了：已经知道幂次是$i$的倍数的元素个数，现在想求出 $\sum$ 幂次最高且恰好为$j$的个数。考虑莫比乌斯反演！ 设 $f_i$ 表示已经知道幂次是 $i$ 的倍数的元素个数，$g_i$ 表示幂次最高且恰好为$j$的个数。 $$ f_i = \sum_{i \mid j} g_j $$ $$ g_i = \sum_{d} \ \mu_{d} \times f_{i \ \times \ d} $$ 那么时间复杂度为$O(q \times 60 \times \log(60))$，虽然有点极限，但是可以过去的，接下来说几个卡常方法： 1.预处理出 $\mu$ 以及可以表示成幂次$>=3$的数 2.如果算$f$的时候枚举的幂次$=2$，则直接用$\sqrt{l}

3.算f枚举幂次的时候可以在对应幂次的数二分了

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
#define int long long
const int INF = 1e18;

bool vis[105];
int mu[105], f[105];
vector<int> prime, pw[66];

int qp(int a, int b){
    int ans = 1;
    while(b){
        if(b % 2){
            if(INF / ans < a) return INF + 1;
            ans *= a;
        }
        b /= 2;
        if(b == 0) return 0;
        if(INF / a < a) return INF + 1;
        a = a * a;
    }
    return 0;
}

int sum(int x){
    if(x <= 1ll) return x;
    f[2] = sqrtl(x);
    for(int i = 3; i < 60; i++){//算f
        int p = upper_bound(pw[i].begin(), pw[i].end(), x) - pw[i].begin();
        f[i] = p - 2;
    }

    int ans = 1;
    for(int i = 2; i <= 60; i++){ //算g
        for(int j = i; j <= 60; j += i){
            ans += mu[j / i] * f[j];
        }
    }
    return ans;
}

inline int read(){
    int x = 0;
    char op = getchar();
    while(op < '0' || op > '9') op = getchar();
    while(op >= '0' && op <= '9'){
        x = x * 10 + (op - '0');
        op = getchar();
    }
    return x;
}
signed main(){
    for(int i = 3; i <= 60; i++){ //预处理出幂次
        int l = 2, r = 1000000000, ans = 0;
        while(l <= r){
            int mid = (l + r) / 2;
            if(qp(mid, i) <= INF){
                l = mid + 1, ans = mid;
            } else {
                r = mid - 1;
            }
        }
        for(int j = 1; j <= ans; j++) {
            pw[i].push_back(pow(j, i));
        }
    }

    mu[1] = 1;
    for(int i = 2; i <= 100; i++){//算莫比乌斯函数
        if(!vis[i]){
            prime.push_back(i);
            mu[i] = -1;
        }
        for(int j = 0; j < prime.size(); j++){
            if(i * prime[j] > 100) break;
            if(i % prime[j] == 0){
                mu[i * prime[j]] = 0;
                vis[i * prime[j]] = 1;
                break;
            } else {
                vis[i * prime[j]] = 1;
                mu[i * prime[j]] = mu[i] * (-1);
            }
        }
    }

    int q, l, r;
    q = read();
    while(q--){
        l = read(), r = read();
        printf("%lld\n", sum(r) - sum(l - 1));
    }
    return 0;
}