如何高效查找区间[l,r]内仅可表示为p次幂的数？

我来帮你梳理如何用容斥原理实现这个需求。首先咱们明确核心目标：找出区间[l, r]里的数x，满足x可以表示为某个整数的p次幂，但不能表示为任何其他大于1的正整数k次幂（k≠p）——就像你举的例子，区间1-20、p=2时，4和9符合要求，但16因为能表示为2^4，所以被排除。

核心思路：转化为本原指数问题 #

首先我们需要一个关键定义：对于大于1的整数x，它的本原指数是满足x = c^m的最大正整数m（比如16的本原指数是4，因为16=2^4，且没有更大的m能让16写成某个整数的m次幂）。而1的本原指数是1，因为它可以表示为任何整数的任何次幂。

我们要找的数，恰好是本原指数等于p的数：

• 如果x的本原指数是p，那么它只能表示为k次幂当且仅当k是p的约数。当p是质数时，唯一的大于1的约数就是p本身，所以这类数只能表示为p次幂；
• 如果x的本原指数是k>p且p整除k（比如16的本原指数是4，p=2），那么x可以表示为p次幂（16=4^{2），但同时也能表示为k次幂（16=2}4），所以不符合要求。

容斥原理的具体实现步骤 #

我们用f(m)表示区间[l, r]中m次幂的数的个数，用ans(m)表示区间中本原指数恰好等于m的数的个数。我们的目标就是计算ans(p)。

1. 计算f(m)的公式

你提到的公式需要一点修正，来正确计数（同时处理浮点数精度和溢出问题）：

long long compute_f(long long l, long long r, int m) {
    if (m == 0) return 0;
    // 计算r的m次根的向下取整，修正精度误差
    long long a = (long long)floor(powl((long double)r, 1.0/m));
    // 用__int128避免幂次计算溢出，验证并修正a
    while (true) {
        __int128 pow_a = 1;
        bool overflow = false;
        for (int i=0; i<m; i++) {
            pow_a *= a;
            if (pow_a > r) { overflow = true; break; }
        }
        if (overflow) { a--; }
        else {
            __int128 pow_a_plus_1 = 1;
            for (int i=0; i<m; i++) {
                pow_a_plus_1 *= (a+1);
                if (pow_a_plus_1 > r) { break; }
            }
            if (pow_a_plus_1 <= r) { a++; }
            else { break; }
        }
    }

    // 计算l的m次根的向上取整，修正精度误差
    long long b = (long long)ceil(powl((long double)l, 1.0/m));
    while (true) {
        __int128 pow_b = 1;
        bool overflow = false;
        for (int i=0; i<m; i++) {
            pow_b *= b;
            if (pow_b > r) { overflow = true; break; }
        }
        if (!overflow && pow_b < l) { b++; }
        else {
            if (b == 0) break;
            __int128 pow_b_minus_1 = 1;
            bool overflow_minus = false;
            for (int i=0; i<m; i++) {
                pow_b_minus_1 *= (b-1);
                if (pow_b_minus_1 > r) { overflow_minus = true; break; }
            }
            if (!overflow_minus && pow_b_minus_1 >= l) { b--; }
            else { break; }
        }
    }

    return max(0LL, a - b + 1);
}

这里用__int128是为了避免高次幂计算时溢出，如果你的语言不支持大整数类型，可以用循环乘法逐步验证，避免溢出。

2. 用容斥计算ans(m)

根据容斥原理，f(m)是所有本原指数为m的倍数的数的总和，因此：
ans(m) = f(m) - sum(ans(k))，其中k是m的真倍数（即k>m且m整除k），且f(k) > 0（也就是区间内存在k次幂的数）。

具体实现时，我们需要：

• 先找出所有满足m >= p且f(m) > 0的m（也就是p的倍数，直到2^m > r为止，因为更大的m不会有对应的数）；
• 按照从大到小的顺序计算ans(m)：因为计算ans(m)需要用到它的真倍数的ans值，先算大的m，再算小的，最后就能得到ans(p)。

比如你举的例子，区间[1,20]、p=2：

• 先列出所有2的倍数且f(m)>0的m：2,4,6,8,...（直到f(m)=1，也就是只有1这个数）；
• 计算ans(8)=f(8)-sum(ans(16), ...)=1-1=0；
• ans(4)=f(4)-ans(8)-ans(12)-...=2-0-0-...=1（对应数16）；
• ans(2)=f(2)-ans(4)-ans(6)-ans(8)-...=4-1-0-0-...=2（对应数4和9），正好符合预期。

关键注意事项 #

• 浮点数精度问题：直接用powl计算根可能有误差，一定要用幂次验证来修正结果，避免漏数或多数；
• 溢出问题：计算高次幂时（比如1e18的30次根），普通整数类型会溢出，需要用大整数类型或者循环乘法来验证；
• 特殊情况处理：当p=1时，我们要找的是不能表示为任何大于1的次幂的数，这时候ans(1)=f(1)-sum(ans(k))（k从2开始），而f(1)=r-l+1（所有数都是1次幂）；
• 数字1的处理：1的本原指数是1，所以它不会被计入任何ans(p)（p>1），会在容斥过程中被减去。

内容的提问来源于stack exchange，提问作者Sathyaram