HDU 2204 / 容斥原理

Posted on 2018-09-01 Views:

题面

大意：求在 [1, n] 中可以表示为 m^k 形式的数的个数（ $m, k \in \mathbb{Z}^+, k > 1,n \le 10^{18}$ ）

这道题不像是有 O(1) 的解法，但是哪怕是 $O(\sqrt{n})$ 的算法也会超时，因此直觉上我们应该寻找的是 $O(\log n)$ 的算法。

首先，因为 m = 1 的情形是trivial的，所以考虑 $m \ge 2$ 此时 $k \le \log_m n \le \log_2 n \le 60$ ，这也是的一个上界。

接下来我们发现：如果一个数可以表示为 m^4 的形式，也一定可以表示为 (m^2)^2 的形式，类似地，如果 k = pq 是合数的话，那么 m^k 一定可以表示为 (m^p)^q 和 (m^q)^p 。

令 P(i) 表示可以表示为 m^i 形式的数的个数，那么题目显然要我们求的是：

$\left| \bigcup_{素数p\le\log_2n}P(p) \right|$

接下来就用容斥原理很快就能解决这道题了，代码非常的简洁，注意精度：

#include <cstdio>
#include <cmath>

using namespace std;
typedef long long ll;
const double EPS = 1e-8;
const int p[] = { 0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 };
ll n;

ll calc(ll d, ll a) {
    if (a > 60) return 0;
    if (d == 0) 
        return a == 1 ? 0 : (ll)(pow(n, 1.0 / a) + EPS) - 1;
    return calc(d - 1, a) - calc(d - 1, a * p[d]);
}

int main() {
    while (scanf("%lld", &n) != EOF)
        printf("%lld\n", -calc(17, 1) + 1);
    return 0;
}