CF955C Sad Powers

· · 题解

CF955C Sad powers

Luogu CF955C

Solution

2023 春赛观光团。

对于一个询问 [l,r]，显然可以拆成 [1,r]-[1,l-1] 两部分计算。

考虑 [1,n] 如何计算。由于指数的值域很小，因此可以考虑枚举指数来计算答案。

记 f_i 表示满足 a_i\le n 的数量（不考虑与其他指数重复的情况），那么显然可以得知 f_i=\sqrt[i]{n}。考虑如何容斥掉重复的部分，直接容斥貌似不好做，因此考虑钦定一个数的唯一指数表示方式。

对于一个数 t，假设 t=a_1^{p_1}=a_2^{p_2}(p_1>p_2)，那么将 t 的表示方法钦定为 t=a_1^{p_1}，即指数最大的一个。容易发现，对于所有可以组成 t 的指数 p 都有 p_i \mid p_1。那么按照这种钦定方法下，记每个指数对答案的贡献是 \text{ans}_i，那么有 \text{ans}_i=f_i-\displaystyle \sum\limits_{i\mid j}\text{ans}_j。从大到小计算即可。时间复杂度是 \mathcal O(\log^2 n) 级别的。

代码实现的时候有一个很麻烦的东西，就是 \sqrt[i]{n} 如何计算。如果使用 n^{1/i} 计算会出现很大的精度问题；如果用二分计算的话时间会超时。因此有一个折中的办法，就是先用 n^{1/i} 计算，然后再暴力判断计算出来的这个值 v 接近的值是否满足答案，即判断一下 v+1,v-1,v+2,v-2,\dots 是否符合条件，然后卡一下精度就过了。

Code

#include<bits/stdc++.h>
#define int long long

using namespace std;

int l, r;
int a[100005];

inline long double Qpow(int x, int y) {
    long double res = 1, base = x;

    for (; y; y >>= 1, base *= base) {
        if (y & 1) {
            res *= base;
        }
    }

    return res;
}

inline int GetRoot(int x, int y) {
    int v = powl(x, (long double)1.0 / y + 1e-9);

    if (Qpow(v + 1, y) < x) 
        for (++v; Qpow(v + 1, y) < x; ++v);

    if (Qpow(v, y) > x)
        for (--v; Qpow(v, y) > x; --v);

    return v;
}

int Calc(int n) {
    if (n == 0) return 0;

    int res = 1;
    int lim = 0;

    for (int i = 2; ; ++i) {
        int v = GetRoot(n, i);
        lim = i;

        if (v <= 1) break;

        a[i] = v - 1;
    }

    for (int i = lim - 1; i >= 2; --i) {
        for (int j = i + i; j < lim; j += i) {
            a[i] -= a[j];
        }
    }

    for (int i = 2; i < lim; ++i) {
        res += a[i];
    }

    return res;
}

void Solve() {
    cin >> l >> r;
    cout << Calc(r) - Calc(l - 1) << '\n';
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T; cin >> T;

    while (T--) Solve();
}